[PS] BOJ 1197 / 최소 스패닝 트리

[PS] BOJ 1197 / 최소 스패닝 트리
문제 링크: https://www.acmicpc.net/problem/1197
Thumbnail: Photo by Marjan Blan (Unsplash)

정석적인 최소 신장 트리(MST; Minimum Spanning Tree)를 구하는 문제입니다.

풀이

크루스칼(Kruskal) 알고리즘

MST를 구하는 알고리즘은 대표적으로 크루스칼 알고리즘과 프림 알고리즘이 존재합니다.

보통 희소 그래프의 경우 크루스칼이, 밀집 그래프의 경우 프림 알고리즘이 더 유리합니다. 이 문제는 최대 10,000개의 정점에 대해 최대 100,000개의 간선이 주어지므로 희소 그래프라고 판단해 크루스칼 알고리즘으로 구현했습니다.

크루스칼 알고리즘에 대한 자세한 설명은 이전 글을 참고해주세요!

전체 코드

input = open(0).readline
V, E = map(int, input().split())
edges = sorted((tuple(map(int, input().split())) for _ in range(E)), key=lambda e: e[2])

# Union-Find
parents = [i for i in range(V + 1)]

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

def union(x, y):
    parent_x = find_parent(x)
    parent_y = find_parent(y)

    if parent_x != parent_y:
        parents[parent_y] = parent_x
        return True
    return False

# Kruskal
total_weight = 0
for x, y, w in edges:
    if union(x, y):
        total_weight += w

print(total_weight)

solution.py