[BOJ] 1197번 : 최소 스패닝 트리(Kruskal)

접근

주어진 그래프에서, 가중치가 최소가 되도록 하는 모든 정점을 연결하는 부분 그래프를 구하는 문제이다.

최소 스패닝 트리는 대표적으로 Kruskal 알고리즘을 활용할 수 있다.

 

Kruskal 알고리즘은 아래와 같은 절차를 따른다.

• 간선들의 가중치를 오름차순으로 정렬
• 오름차순으로 간선들의 탐색을 진행하며, 사이클을 만들지 않는 정점들을 연결
• 포함된 간선의 갯수가 `정점의 갯수 - 1` 가 되면 종료

Kruskal 알고리즘을 진행할 때, 사이클을 체크하는 과정은 대표적으로 Union-Find 알고리즘을 활용한다. 간단하게 생각하면 A-B 친구, B-C 친구, A-C? => 친구 이런식의 해결방법이다. 아래는 알고리즘 진행에 대한 좋은 설명 자료이다.

 

https://commons.wikimedia.org/wiki/File:MST_kruskal_en.gif

 

해결

Kruskal 알고리즘과 Union-Find를 이용해서 해결한다. 

Union-Find는 재귀적으로 Root Node를 찾는 `Find`, Root Node를 수정하는 `Union` 함수로 구성되어 있다.

Union-Find는 서로소 집합(분리 집합, disjoint set)를 찾기 위해 트리 형태로 인식해서 해결하는 방법이다.

초기엔 자기 자신을 Root Node로 모두 지정해주고, 간선을 탐색하면서 Root Node를 수정해나간다. 일반적으로는 정점이 작은 Node를 Root로 변경해준다고 하더라.

해당 내용자체로만 너무 길어질 수 있어, 나중에 다시 전반적인 알고리즘과 최적화 과정을 정리해보도록 하겠다.

코드

V, E = map(int, input().split())
edges = []

for _ in range(E):
    A, B, C = map(int, input().split())
    edges.append((C, (A, B)))
    
edges = sorted(edges, key=lambda x : x[0])
parents = [i for i in range(V+1)]

def find(x):
    if parents[x] == x:
        return x
    else:
        parents[x] = find(parents[x])
        return parents[x]
    
def union(x, y):
    x = find(x)
    y = find(y)
    
    parents[y] = x
    
    
spanning_dist = 0
e_num = 0
for w, (a, b) in edges:
    if find(a) != find(b):
        spanning_dist += w
        e_num += 1
    
    union(a, b)
    
    if e_num == E-1:
        break
        
print(spanning_dist)