그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.
최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.
그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.
첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.
3 3
1 2 1
2 3 2
1 3 3
3
스패닝 트리란, 모든 노드들 간의 서로 연결은 되어있되 사이크링 존재하지 않는 부분 그래프를 의미한다.
최소 스패닝 트리 ⊂ 스패닝 트리
이처럼 최소 스패닝 트리는 가중치의 합을 최소로 하는 스패닝 트리를 말한다.
이 문제를 해결하기 위해 가장 많이 사용되는 알고리즘은 Kruskal 알고리즘이다.
1197문제의 경우 최소 스패닝 트리 문제는 정점도 많고, 가중치가 음수가 될 수 있을 뿐 아니라, 근본적으로 스패닝 트리를 만드는 과정에서 간선이 바뀔 수 있기 때문에 Union-Find 활용
위와 같이 1과 2과 연결되어 있고 나머지 노드들이 자유 분방하게 존재한다고 생각해봅시다.
위와 같이 2번째 인덱스의 값에 1이 들어가는 것을 표현하여 연결성을 표현할 수 있다.(일반적으로 부모를 합칠 때에는 더 작은 값쪽으로 합친다)이것이 바로 Union-Find이다.
import sys
input = lambda: sys.stdin.readline().rstrip()
V, E = map(int, input().split())
# Kruskal Algorithm
# https://techblog-history-younghunjo1.tistory.com/262
edges = []
for _ in range(E):
A, B, C = map(int, input().split())
edges.append((A, B, C))
edges.sort(key=lambda x: x[2]) # C(Cost)가 적은 것부터 정렬
# Union-Find
parent = [i for i in range(V+1)]
def get_parent(x):
if parent[x] == x:
return x
parent[x] = get_parent(parent[x]) # get_parent 거슬러 올라가면서 parent[x] 값도 갱신
return parent[x]
def union_parent(a, b):
a = get_parent(a)
b = get_parent(b)
if a < b: # 작은 쪽이 부모가 된다. (한 집합 관계라서 부모가 따로 있는 건 아님)
parent[b] = a
else:
parent[a] = b
def same_parent(a, b):
return get_parent(a) == get_parent(b)
answer = 0
for a, b, cost in edges:
# cost가 작은 edge부터 하나씩 추가해가면서 같은 부모를 공유하지 않을 때(사이클 없을 때)만 확정
if not same_parent(a, b):
union_parent(a, b)
answer += cost
print(answer)