Python 백준 알고리즘 1197 : 최소 스패닝 트리

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

1197번: 최소 스패닝 트리

 

# 1197 최소 스패닝 트리

v, e = map(int, input().split())
parent = [0] * (v+1)
edge = []
sum = 0
for i in range(1, v+1):
  parent[i] = i

def find(x):
  if parent[x] != x:
    parent[x] = find(parent[x])
  return parent[x]

def union(a, b):
  a = find(a)
  b = find(b)
  if a < b:
    parent[b] = a
  else:
    parent[a] = b

for _ in range(e):
  a, b, cost = map(int,input().split())
  edge.append((cost, a, b))

edge.sort()

for cost, a, b in edge:
  if find(a) != find(b):
    union(a, b)
    sum += cost

print(sum)

 

최소 스패닝 트리는 스패닝 트리의 간선들의 합이 최소가 되는 스패닝 트리이다. 스패닝 트리는 사이클 없이 모든 정점이 연결되어 있는 트리이다. 스패닝 트리의 간선의 개수는 v(모든 정점의 개수) - 1이다.

최소 스패닝 트리를 구하는 방법으로 크루스칼 알고리즘이 있는데 아래 링크를 참조했다.

 

https://techblog-history-younghunjo1.tistory.com/262

[Python] 최소 신장 트리를 찾는 크루스칼(Kruskal) 알고리즘

 

크루스칼 알고리즘의 과정은

 

1. 모든 간선 정보에 대해 오름차순으로 정렬 수행

2. 이후에 간성 정보를 하나씩 꺼내어 사이클이 발생하는지 확인

3. 사이클이 발생한다면 최소 스패닝 트리에 포함시키지 않고, 사이클이 발생하지 않는다면 최소 스패닝 트리에 포함 시킴

 

이 과정을 반복하는데 2번에서 사이클이 발생하는지 확인하는 방법은 예전에 공부했던 유니온-파인드를 이용해서 사이클이 발생하는지 확인할 수 있다.