마을과 임의의 두 마을 사이의 거리가 주어질 때, 모든 마을을 연결하는 최소 비용의 가로등 설치 비용을 반환한다.
가로등은 두 마을 사이의 거리만큼의 비용이 든다.
💻Solution
import heapq
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
parent[max(a,b)] = min(a,b)
while True:
n, m = map(int, input().split())
if n == 0 and m == 0:
break
parent = [i for i in range(n+1)]
total_cost = 0
result = 0
q = []
for _ in range(m):
x, y, z = map(int, input().split())
total_cost += z
heapq.heappush(q, (z, x, y))
while q:
cost, a, b = heapq.heappop(q)
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
result += cost
print(total_cost - result)
🗝️keypoint
크루스칼 알고리즘을 통해 최소 비용으로 모든 마을을 연결하는 그래프를 완성한다.
절약한 비용은 모든 마을의 가로등 비용에서 마을을 연결하는 최소 비용을 제하여 구할 수 있다.