문제정리)
각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때, 모든 컴퓨터를 연결하는데 필요한 최소비용을 찾으면 된다.
📌 크루스칼 알고리즘을 사용해보자!
크루스칼 알고리즘은 그래프 내의 모든 정점들을 가장 적은 비용으로 연결하고자 할 때 사용된다.
즉, 최소 신장 트리를 찾는 알고리즘
앞에서 푼 유니온 파인드도 사용한다.
모든 간선에 대한 비용을 오름차순으로 정렬한 후, 첫 번째 원소부터 확인하면서 사이클이 발생하지 않는 경우에만 연결하면 된다.
즉 여기서 사이클이 발생하는지 확인할 때 파인드 함수, 연결할 때 유니온 함수를 쓰면 된다.
n = int(input())
m = int(input())
parent = list(range(n + 1))
edges = []
result = 0
def find_parent(x):
if parent[x] != x:
parent[x] = find_parent(parent[x])
return parent[x]
def union(a, b):
a = find_parent(a)
b = find_parent(b)
if a < b:
parent[b] = a
else:
parent[a] = b
for _ in range(m):
a, b, c = map(int, input().split())
edges.append((a, b, c))
edges.sort(key = lambda x:x[2]) # 비용을 기준으로 정렬
for i in range(m):
a, b, c = edges[i]
if find_parent(a) == find_parent(b):
continue
union(a, b)
result += c
print(result)