🔗 Problem Link

 

6497번: 전력난

성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들

www.acmicpc.net


❔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. 절약한 비용은 모든 마을의 가로등 비용에서 마을을 연결하는 최소 비용을 제하여 구할 수 있다.

+ Recent posts