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

📖 문제

1197번: 최소 스패닝 트리

 

🔎 풀이

유니온 파인드를 활용하는 최소 신장 트리 문제입니다. 모든 정점들을 연결하면서, 가중치의 합을 최소로 만들기 위해서는 사이클을 만들지 않아야 합니다. 이는 크루스칼 알고리즘으로 잘 알려져 있습니다. 풀이 방법은 가중치가 가장 작은 간선부터 하나씩 사이클을 만들지 않으면서 각 노드를 연결하는 것입니다. 이때 사이클을 판단하는 과정은 유니온파인드를 이용합니다.

 

💻 코드

import sys
input = sys.stdin.readline

V, E = map(int, input().split())
graph = []
root = [int(x) for x in range(V+1)]
for _ in range(E):
    A, B, C = map(int, input().split())
    graph.append((C, A, B))
    graph.append((C, B, A))

# 두 정점 사이의 경로가 짧은 순서대로 정렬
graph.sort()

# root를 찾는 함수
def find_parents(x):
    if root[x] == x:
        return x
    return find_parents(root[x])

# root를 통합하는 함수
def union(a, b):
    a = find_parents(a)
    b = find_parents(b)
    if a < b:
        root[b] = a
    else:
        root[a] = b


cost = 0
# 거리 비용, 출발 노드, 도착 노드
for k, i, j in graph:
    # 두 노드의 root가 같지 않다면 거리비용 추가하고 root 합치기
    if find_parents(i) != find_parents(j):
        cost += k
        union(i, j)

print(cost)