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

문제 링크 : https://www.acmicpc.net/problem/1197

MST (Minimum Spanning Tree) 문제. 스패닝 트리란 하나의 그래프 G가 있을 때, G의 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.

그러면 G에서 만들 수 있는 스패닝 트리는 여러가지가 존재할 수 있게 되는데, 이 중 최소비용으로 만들 수 있는 스패닝 트리를 MST 라고 한다.

대표적인 MST를 찾는 알고리즘에는 크루스칼 알고리즘이 있다.

크루스칼 알고리즘
1. 간선 데이터를 비용을 기준으로 오름차순 정렬한다.
2. 간선을 하나씩 확인하며 현재 간선이 사이클을 발생시키는지 체크한다.
2-a. 사이클이 발생하지 않는 경우 MST에 포함시킨다.
2-b. 사이클이 발생하는 경우 MST에 포함시키지 않는다.
3. 모든 간선에 대해 1~2번 과정을 반복한다.

기억할 것

1. 최소 스패닝 트리 문제는 크루스칼 알고리즘으로 풀 수 있다.
2. 크루스칼 알고리즘에는 Union-Find의 개념이 들어간다.

파이썬 코드

import sys
sys.setrecursionlimit(10**6)
V, E = map(int, sys.stdin.readline().split())
parent = [x for x in range(V+1)]
edges = []

for _ in range(E):
    A, B, C = map(int, sys.stdin.readline().split())
    edges.append((A, B, C))


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


def union(a, b):
    pa = find_parent(a)
    pb = find_parent(b)

    if pa < pb:
        parent[pb] = pa
    else:
        parent[pa] = pb


answer = 0
edges.sort(key=lambda x: x[2])

for edge in edges:
    x, y, cost = edge[0], edge[1], edge[2]
    # 사이클을 만들면 무시
    if find_parent(x) == find_parent(y):
        continue

    union(x, y)
    answer += cost


print(answer)