[Graph] MST - Kruskal Algorithm - 백준

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

Minimum Spanning Tree 문제가 무엇이며 이를 푸는 대표적인 알고리즘으로 사용되는 Kruskal 알고리즘에 대해 공부해보자

 

이 외에도 Prim Algorithm도 있으니 추후에 정리하자. 

 

한다성 교수님 강의자료

MST는 최소 연결 부분 그래프라고 이해하면 된다. 

여기서 최소의 의미는 edge의 가중치의 합이 가장 적은 경우를 의미한다!

• 신장트리는 최소 연결 부분 그래프 [ 이 중 가장 weight가 적은 녀석으로 ]
• 모든 정점들이 연결되어 있어야 하고 cycle이 있으면 안됨!
• n개의 vertex, n-1의 edge

이러한 MST 문제는 다음과 같은 실생활 문제를 해결할 때 사용된다.

• 컴퓨터, 통신망 네트워크 문제
• 최적화 문제
• 상하수도 공급망 형성 문제 등에 사용

 

이 문제를 해결하기 위해 Kruskal 알고리즘은 

"정렬" 과 "disjointset" 알고리즘을 사용한다.

 

우선 모든 edge들을 가중치를 기준으로 정렬을 해준 다음, 

그래프를 만들어가는데 이 때 cycle check를 해주기 위해 disjointset 알고리즘을 사용한다.

 

예를 들어보자

 

우선 다음과 같은 그래프가 있다고 가정해보자

이 예제에서 MST를 찾고자 한다.

 

Union Find는 MST 구축 시 Cycle Check를 위해 사용되는데,

 

어떤 식으로 Cycle check를 하는 지 알아보자

우선 다음과 같이 그래프가 구성된다고 보자

이러한 그래프가 있을 때

Union Find에서 수행한 것처럼 우선 각 노드의 "부모"와 "랭크"를 초기화해준다.

 

parent = { 1: 1, 2: 2, 3: 3, 4: 4, 5: 5 }

rank = { 1 : 0, 2 : 0, 3 : 0, 4 : 0, 5 : 0 }

 

우선 여기서 edge별로 살펴보면서 하나씩 확인해보자

1과 2를 확인

각 노드의 부모를 찾는다. → Find ( Path Compression )

이 경우 1의 부모는 1, 2의 부모는 2

여기서는 부모가 다르다 → 따라서 Union을 수행해서 하나의 집합으로 합친다.

 

다음으로 3을 보자

 

4, 5도 마찬가지로 별도의 서로소 집합을 구축한다.

그런데 여기서, 만약 2와 3을 연결한다고 해보자!

 

이러한 메커니즘으로 cycle check를 하게 된다

 

그렇다면 저 edge들을 어떤 순서대로 볼까?

크루스컬은 바로 저 edge들을 "weight가 작은 순"대로 살펴보는 것이 핵심이다. 

 

즉 위 그림의 예제도 다음과 같이 선택할 수 있는 것이다.

 

이러한 방법으로 동작을 수행한다.

 

정렬이 대부분의 시간 cost를 차지하기 때문에 크루스컬의 시간 복잡도는 다음과 같다.

 

Kruskal Algorithm

---

• 모든 Edge들의 정보를 담은 list를 정렬해준다!!! → 시간 복잡도 O(nlogn)
• Cycle Check를 하기 위해 Union Find Algorithm을 사용한다!! —> edge*G(n)

 

이러한 메커니즘으로 다음 문제를 풀이한 결과는 다음과 같다.

 

V, E = [int(x) for x in input().split()]

graph = [ [int(x) for x in input().split()] for _ in range(E) ]

def Union(x,y) :
    if rank[x] > rank[y] :
        parent[y] = x
        rank[x] += 1
    if rank[x] < rank[y] :
        parent[x] = y
        rank[y] += 1
    else :
        parent[y] = x
        rank[x] += 1

def Find(u) :
    if parent[u] != u :
        parent[u] = Find(parent[u])
    return parent[u]

kruskal_graph = []
parent= {}; rank = {}
for i in range(1,V+1) :
    parent[i] = i
    rank[i] = 0
    
answer = 0

for u, v, c in sorted(graph, key= lambda x : x[2]) :
    u_parent = Find(u); v_parent=Find(v)
    if u_parent != v_parent :
        Union(u_parent, v_parent)
        kruskal_graph.append([u,v,c])
        answer += c
    
#print(kruskal_graph)
print(answer)