[이코테] 그래프

✅ 서로소 집합 표현

- union / find 연산 수행

- 부모 테이블을 따로 둬서 부모 노드를 기록

ex) union 1,4

4 의 부모가 4에서 1로 변경

 

union 2, 3

3의 부모가 3에서 2로 변경

 

union 2,4

4의 부모는 더 작은 2로 그대로 둠

 

⌨️ 소스코드

def find_parent(parent, x):
	if parent[x] != x:
    	return find_parent(parent, parent[x])
    return x

def union_parent(parent, a, b):
	a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a<b:
    	parent[b] = a
    else:
    	parent[a] = b
   
   	v, e = map(int,input().split())
    parent = [0]*(v+1)
    
    # 부모를 자기 자신으로 초기화
    for i in range(1, v+1):
    	parent[i] = i
    
    # union 연산 수행
    for i in range(e):
    	a, b = map(int,input().split())
        union_parent(parent, a, b)

 

⏰ 시간복잡도

- 노드의 루트 노드를 찾기 위해서 거슬러 올라가야 하기 때문에 O(V) 의 시간이 소요될 수 있음. 

 

경로 압축을 이용해서 최적화 가능.

find 를 재귀적으로 호출한 뒤에 부모 테이블 값을 갱신하는 기법.

 

def find_parent(parent, x):
	if parent[x] != x:
    	parent[x] = find_parent(parent, parent[x])
    return parent[x]

 

이렇게 갱신할 경우, 부모 테이블의 접근을 통해서 바로 루트 노드를 알 수 있음.

 

방향성이 없는 경우, 사이클 판별도 가능!

 

각 간선을 통해서 루트 노드를 확인하고, 루트 노드가 서로 다르다면 union 연산을 수행하고 루트 노드가 같다면 사이클이 발생한 것으로 판별.

 

for i in range(e):
	a, b = map(int,input().split())
    if find_parent(parent, a) == find_parent(parnet, b):
    	cycle = True
        break
    else:
    	union_parent(parent, a, b)

 

✅ 신장 트리

- 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

ex) N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시에 연결될 수 있도록 할 때

 

✅ 크루스칼 알고리즘

- 모든 간선을 정렬하고, 거리가 짧은 간선부터 집합에 포함시킴

- 사이클을 발생시킬 수 있는 간선은 포함시키지 않음.

- 같은 집합에 포함되지 않는 경우 (사이클을 발생시키지 않는 경우) 사이클 연산을 수행하도록 함

 

⌨️ 소스코드

#루트 노드 찾기
def find_parent(parent, x):
	if parent[x] != x:
    	parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b);
	a = find_parent(parent, a)
    b = find_parent(parent, b)
    
    if a < b:
    	parent[b] = a
    else:
    	parent[a] = b
 
 # 중략 . . .
 
edges = []
result = 0

for i in range(1, v+1):
	parent[i] = i
    
for _ in range(3):
	a, b, cost = map(int, input().split())
    edges.append((cost, a, b))
    
edges.sort()

for edge in edges:
	cost, a, b = edge
    if find_parent(parent, a) != find_parent(parent,b)
    	union_parent(parent, a, b)
        result += cost

⏰ 시간복잡도 O(E logE)

간선을 정렬하는 데에 가장 시간이 오래 걸림

 

---

 

✅ 위상 정렬

- 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것

1. 진입차수가 0인 노드를 큐에 넣음

2. 큐가 빌 때까지 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거 / 새롭게 진입차수가 0이 된 노드를 큐에 넣음

 

⌨️ 소스코드

from collections import deque

v, e = map(int,input().split())
indegree = [0] * (v+1)
graph = [[] for i in range(v+1)]

for _ in range(e):
	a, b = map(int,input().split())
    graph[a].append(b) #a 에서 b 로 이동할 수 있다는 뜻!
    indegree[b] +=1

def topology_sort():
	result = []
    q = deque()
    
    for i in range(1, v+1): #진입차수가 0인 노드를 큐에 삽입
    	if indegree[i] == 0:
        	q.append(i)
    
    while q:
    	now = q.popleft()
        result.append(now)
    
    	for i in graph[now]:
        	indegree[i] -= 1
         	if indegree[i] == 0:
            	q.append(i)

⏰ 시간복잡도 O(V+E)

- 간선을 차례대로 제거해야 함

 

---

🧐 팀 결성

# p.298 팀 결성

def find_parent(parent, x):
    if parent[x]!= x:
        find_parent(parent, parent[x])
    return parent[x]

def union(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

n,m = map(int,input().split())

parent = [0 for _ in range(n+1)]

for i in range(n+1):
    parent[i] = i

for _ in range(m):
    cal, a, b = map(int,input().split())
    if cal == 0:
        union(parent, a, b)
    else:
        if find_parent(parent, a) == find_parent(parent, b):
            print("YES")
        else:
            print("NO")

🧐 도시 분할 계획

# p.300 도시 분할 계획

'''
n개의 집과 m개의 길
2개로 분할하기
'''

def find_parent(parent, x):
    if parent[x] != x:
        find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

n,m = map(int,input().split())
parent = [0 for _ in range(n+1)]

for i in range(n+1):
    parent[i] = i

edges = []

for _ in range(m):
    a, b, c = map(int,input().split())
    edges.append(c, a, b)

edges.sort()
last = 0
result = 0

for edge in edges:
    cost, a, b = edge
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost
        last = cost

print(result - last)

두개의 도시로 만들기 위해서 크루스칼 알고리즘을 이용해 가장 비용이 낮은 간선부터 더하고, 가장 큰 값인 last 를 빼주면 두개의 신장 트리를 얻을 수 있다