백준 1197 최소 스패닝 트리준 1197 최소 스패닝 트리

문제 정보

문제링크
최소 스패닝 트리(최소 신장 트리)를 구했을 때의 가중치를 구하는 문제이다.

배경 지식

스패닝 트리는 다음의 조건을 만족하는 트리를 의미한다.

(1) 모든 정점을 포함하고,
(2) 정점 간 서로 연결이 되는 트리

그리고 트리의 조건을 분리하면
(3) 싸이클이 존재하지 않는 그래프

까지 세 가지 조건을 의미한다.

이 때 간선들의 가중치가 제시되어 있고, 해당 간선들의 비용 중 최소의 비용을 만족하는 최소 신장 트리를 구하는 대표적인 알고리즘은 크루스칼 알고리즘과 프림 알고리즘이다.

크루스칼 알고리즘과 프림 알고리즘

알고리즘	핵심 아이디어	시간복잡도	특이사항
크루스칼	간선 정렬 후 사이클 없는 것만 선택	𝑂(𝐸 log𝐸)	Union-Find 사용, 희소 그래프에 유리
프림	현재 정점에서 인접한 최소 간선 선택	𝑂(𝐸 log𝑉)	우선순위 큐 사용, 조밀 그래프에 유리

정점 기준으로 가장 가중치가 작은 간선을 선택할 지,
간선 기준으로 가장 가중치가 작은 간선 중에서 사이클이 없는 것을 선택할지에 따라서
두 알고리즘은 구분이 된다.
정점 대비 간선의 비중에 따라서 선택하면 되는데, 임의의 두 정점에 대해 최대 하나의 간선만 존재할 수 있다는 가정 하에 무방향 그래프의 최대 간선 수 대비 간선의 비율로 계산한다고 한다. GPT의 도움에 따르면 계산식은 다음과 같다.

이 밀도가 0.5 이상이면 조밀, 0.1 이하면 희소한 그래프로 본다고 한다.

문제의 제한사항에 따르면 정점의 최대 개수가 10,000개, 간선의 최대 개수가 100,000개이므로

해당 계산식에 따르면 최악의 경우 밀도는 0.002, 따라서 크루스칼 알고리즘이다.

구현

import sys
import heapq
# input의 특성 상 여러 줄을 읽어와야 할 때 sys.stdin.readline이 더 빠른데
# 해당 문제는 최악의 경우 100,000줄을 읽어와야 하므로 input을 대체
input = sys.stdin.readline
# Recursion Error가 나서 재귀의 한도를 늘렸다. Python의 default 재귀 한도는 10**3
sys.setrecursionlimit(10**5)

# Union Find 구현
def union(n1, n2):
    parents[n2] = n1

def find(n):
    if parents[n] == n:
        return n
    else:
        parents[n] = find(parents[n])
        return parents[n]

v, e = map(int,input().split())
parents = [i for i in range(v+1)]
# 최소 힙으로 쓸 q
q = []

# 사용된 간선의 개수를 세서 불필요한 계산을 막을 변수
# 간선의 개수는 정점의 개수보다 하나 적으므로 초기값으로 1 할당
linked = 1

ans = 0

for _ in range(e):
    s, e, w = map(int,input().split())
    heapq.heappush(q, (w, s, e))

while linked != v:
    w, s, e = heapq.heappop(q)
    s = find(s)
    e = find(e)
    if s != e:
        union(s, e)
        ans += w
        linked += 1

print(ans)