[Python] 백준 1197번: 최소 스패닝 트리

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

 

import sys
input = sys.stdin.readline


def find(x):
    if parents[x] == x:
        return x

    parents[x] = find(parents[x])
    return parents[x]


def union(x, y):
    x, y = find(x), find(y)

    if x < y:
        parents[y] = x
    else:
        parents[x] = y


def getMinSpanningTreeWeight():
    minSpanningTreeWeight = 0

    for a, b, c in vertices:
        if find(a) != find(b):
            union(a, b)
            minSpanningTreeWeight += c

    return minSpanningTreeWeight


if __name__ == '__main__':
    V, E = map(int, input().split())

    parents = [i for i in range(V+1)]

    vertices = [list(map(int, input().split())) for _ in range(E)]
    vertices.sort(key=lambda x: x[2])

    print(getMinSpanningTreeWeight())

 

kruskal의 알고리즘을 이용한다. 해당 알고리즘은 아래와 같이 진행된다.

• weight에 따라 모든 간선들을 오름차순으로 정렬시킨다.
• 정렬된 순서를 기준으로 반복문을 수행한다.
  • 현재 상태에서, 간선이 연결되어있는 두 개의 정점에 대해서, 만약 서로가 같은 집합에 속해있지 않다면(find), 두 정점을 병합(union)하고, 해당 weight을 누적해서 더해준다.

 

정렬된 vertices를 순차적으로 돌면서 조건에 부합할 때마다 선택을 하는 방식이므로, 매우 greedy한 알고리즘이라고 볼 수 있다. 직관적인 이해를 위한 gif 사진은 아래와 같다.

출처: commons.wikimedia.org

 

유니온파인드로 구현을 했으며(통상 이렇게 한다.), 정점이 합쳐질 때마다 weight을 누적하게 되는데, 이것의 최종값을 출력하면 된다.