: 최소 신장 트리(Minimum Spanning Tree)를 구하는 대표적인 알고리즘
하나의 그래프 내에 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
신장트리는 한 그래프 내에서 여러개가 존재하는데 신장트리 중에서 최소한의 비용으로 만들 수 있는 트리를 최소 신장 트리(Minimum Spanning Tree)라고 한다.
이 MST를 구하는 대표적인 알고리즘이 크루스칼 알고리즘이다.
- 주어진 간선들을 가중치를 기준으로 오름차순으로 정렬한다.
- 최소 비용 간선부터 뽑는데 사이클이 발생하는지 체크해야 한다.(union-find)
=> 사이클이 발생할 경우 최소 신장 트리에 포함시키지 않는다.- 2를 모든 간선에 대해 반복한다.
사이클이 발생하는 지 체크할 때 union-find 알고리즘을 사용한다. find 함수를 통해 부모노드를 각각 찾고 부모노드가 다른 경우 서로 다른 집합, 즉 이어져있지 않기 때문에 사이클을 발생하지 않는다. 사이클이 발생하지 않았다면 union 함수를 이용해 노드를 이어준다.
- 모든 지점을 연결하는 네트워크의 최소비용을 구하라.
- 모든 도시를 연결하는 도로의 길이 합이 최소가 되도록 구하라.
###### union-find ######
def find(parent, x):
if parent[x] != x:
parent[x] = find(parent, parent[x])
return parent[x]
def union(parent, a, b):
a = find(parent, a)
b = find(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
###### 크루스칼 알고리즘 ######
v, e = map(int, input().split())
parent = [i for i in range(v+1)]
edges= []
result = 0
# 1. 모든 간선 정보 저장
for _ in range(e):
a, b, cost = map(int, input().split())
edges.append((cost, a, b))
# 2. 가중치를 기준으로 오름차순 정렬
edges.sort()
for edge in edges:
cost, a, b = edge
# 3. 부모 노드가 같으면 cycle 발생
if find(parent, a) != find(parent, b):
union(parent, a, b)
result += cost
print(result)