최소 스패닝 트리(MST)와 크루스칼 알고리즘

최소 스패닝 트리란?

최소 스패닝 트리를 요약하면

간선마다 비용이 정해져 있을 때, 최소 비용으로 모든 노드를 연결한 트리

라고 할 수 있다.

최소 스패닝 트리 예제 1647번 - 도시 분활계획

문제

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.

마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다.

마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.

그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집과 B번 집을 연결하는 길의 유지비가 C (1 ≤ C ≤ 1,000)라는 뜻이다.

출력

첫째 줄에 없애고 남은 길 유지비의 합의 최솟값을 출력한다.

이 문제를 최소 스패닝 트리를 사용해 풀 수 있다는 것을 알고 있으면 자연스럽게 문제 해결 과정이 머리에 떠오를 것이다.

최소 스패닝 트리를 사용해 최소 비용으로 모든 마을을 연결 한 후, 가장 비용이 비싼 길을 하나 제거하면 문제의 조건을 모두 만족시킨다는 것을 알 수 있다.

최소 스패닝 트리를 사용하는 문제라는 것을 알고나면 간단한 문제로 느껴질 수 있지만, 모르는 상태에서 최소 스패닝 트리로 해결할 수 있는 문제라는 것을 깨닫는 것이 어려울 수 있다.

최소 스패닝 '트리' 라는 이름을 한 번 짚고 넘어가야 할 필요가 있다. 트리의 특징 중 하나는 노드의 개수가 N개 일 때 간선의 개수가 반드시 N-1개라는 점이다.

최소 스패닝 트리는 노드 간의 경로를 줄이거나 하는 것에는 관심 없고 '모든 노드가 연결되어 있는 상태'를 만들기 위해 최소한의 비용을 사용하는 것이기 때문에 N-1개보다 많은 간선을 필요로 하지 않아 그래프가 아닌 항상 트리 구조가 되는것이다.

이 점을 이용해서 최소 스패닝 트리를 만드는 Kruskal 알고리즘을 이해해보자.(최소 스패닝 트리를 만드는 알고리즘은 크루스칼 알고리즘과 프림 알고리즘 두가지가 있다)

algorithm Kruskal(G) is
    F:= ∅
    for each v ∈ G.V do
        MAKE-SET(v)
    for each (u, v) in G.E ordered by weight(u, v), increasing do
        if FIND-SET(u) ≠ FIND-SET(v) then
            F:= F ∪ {(u, v)} ∪ {(v, u)}
            UNION(FIND-SET(u), FIND-SET(v))
    return F

위의 코드는 크루스칼 알고리즘의 Pseudocode.(출처)

크루스칼 알고리즘의 원리는 간선을 비용이 낮은 순으로 정렬 한 후 간선의 양 쪽 끝 노드가 이미 같은 그룹에 속한 상태가 아니라면 그 간선을 트리에 붙여나가는 방식이다.

크루스칼 알고리즘의 원리

크루스칼 알고리즘 정확성 증명 엄밀한 증명은 위의 링크를 참고하는것을 추천한다.

위와 같이, 4개의 정점과 3개의 간선으로 만들어진 스패닝 트리가 있을 때, 하나의 간선을 추가 해 보자.

3번과 4번을 잇는 간선을 추가하면 1-2-3-4이 순환하게 되면서 스패닝 트리의 정의에 어긋나게 됐다. 스패닝 트리가 되기 위해서는 다른 간선 하나를 제거해야만 한다.

제거 할 간선을 정하기 위해서 간선의 비용들을 확인해봤다.

비용이 8인 2번 3번 사이의 간선을 제거하고 비용이 8인 3번 4번 사이의 간선을 추가한다면 전체 스패닝 트리를 구성하는 비용이 감소한다.

하지만 이렇게 새로 추가하는 간선이 순환내에 있는 모든 간선들보다 비용이 높다면 어떨까?

이런 상황에서는 새로 추가된 간선을 제거하는 것이 전체 스패닝 트리를 구성하는 비용을 감소하는 방법이 된다. 즉, 처음부터 추가 할 필요가 없어진다는 뜻이다.

바로 이 점이 간선을 비용이 적은 순서대로 간선을 정렬하고 스패닝 트리를 구성하면 최소 스패닝 트리가 된다는 크루스칼 알고리즘의 원리이다.

간선의 비용이 적은 순서대로 추가해가면서 모든 정점이 연결된 스패닝 트리가 완성된 순간, 그 보다 높은 비용의 간선들은 위의 논리에 따라서 다른 간선과 교체되며 들어갈 수 없다는 것을 알 수 있다.

스패닝 트리 만들기

새로 추가되는 간선이 순환을 만들면 해당 간선을 추가 할 수 없기 때문에 순환 발생 여부를 확인해야 한다.

순환 생성 여부는 Union-Find 알고리즘을 사용하여 확인 할 수 있다.

현재 추가된 간선의 상태가 이런 상황이라면, 위의 정점들은 두 개의 그룹으로 나뉘어져 있다.

3번 정점과 6번 정점을 잇는 간선을 추가한다면 순환이 발생한다. 또한, 2번 정점과 5번 정점을 잇는 간선을 추가해도 순환이 발생한다.

즉, 같은 그룹에 속해있는 정점끼리 연결하면 순환이 발생한다.

Union-Find 알고리즘이 그래프에서 두 정점이 같은 그룹에 속하는지 알기 위한 알고리즘이기 때문에 Union-Find 알고리즘을 사용하면 순환 발생 여부를 확인할 수 있다.

구현

from sys import stdin
n, m = map(int, stdin.readline().split())
edges = [0] * m
parents = [i for i in range(n+1)]
cnt = 0
answer = 0
for i in range(m): 
    start, end, cost = map(int, stdin.readline().split())
    edges[i] = [cost, start, end]

edges.sort()

def getParent(node):
    if(parents[node] == node): return node
    return getParent(parents[node])

def union(s, e):
    if (s < e): parents[e] = s
    else: parents[s] = e

for [c, s, e] in edges:
    if (cnt == n-2): break
    sp = getParent(s)
    ep = getParent(e)
    if(sp == ep): continue
    union(sp,ep)
    cnt += 1
    answer += c

print(answer)

위의 코드는 1647번을 풀 때 사용한 코드다.

간선의 비용을 기준으로 간선들을 정렬한 후에 각 간선마다 간선의 양 정점이 같은 그룹에 속하는 지 확인하고 속하지 않는다면 간선의 비용을 answer 값에 추가하고 두 정점을 같은 그룹으로 만들어준다.

반복문의 종료 시점이 n-2인 이유는 최소 스패닝 트리를 만들고 가장 비용이 많은 길 하나를 제거하는것을 마지막 간선을 추가하지 않는것으로 해결했기 때문이다.