[Baekjoon] 6497. 전력난

🔗 Problem Link

6497번: 전력난

---

❔Thinking

• 마을과 임의의 두 마을 사이의 거리가 주어질 때, 모든 마을을 연결하는 최소 비용의 가로등 설치 비용을 반환한다.
• 가로등은 두 마을 사이의 거리만큼의 비용이 든다.

---

💻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

1. 크루스칼 알고리즘을 통해 최소 비용으로 모든 마을을 연결하는 그래프를 완성한다.
2. 절약한 비용은 모든 마을의 가로등 비용에서 마을을 연결하는 최소 비용을 제하여 구할 수 있다.