백준 6497 전력난

문제

전력난

가로등을 소등하며 최소 비용을 구하자

난이도 : Gold4

---

풀이

1. kruskal 알고리즘을 이용해 최소 비용을 계산한다.
2. 절약 에너지를 구해야 하므로 전체 비용에서 최소 비용을 뺀다.

---

코드

import sys

def get_total(d):  # 전체 비용 계산
    total_cost = 0
    for i in d:
        total_cost += i[-1]
    
    return total_cost
    
def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])
    return parent[a]

def union(parent, a, b):
    x = find(parent, a)
    y = find(parent, b)
    if x < y:
        parent[y] = x
    else:
        parent[x] = y
        
def kruskal():
    min_cost = 0
    for i in range(m):
        a, b, cost = data[i]
        if find(parent, a) != find(parent, b):
            union(parent, a, b)
            min_cost += cost
            
    print(get_total(data) - min_cost)  # 절약되는 에너지 출력이므로 모든 cost에서 mst cost를 빼준다.
    
while True:
    n, m = map(int, sys.stdin.readline().split())
    if n == 0 and m == 0:
        break
    
    data = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]
    parent = [i for i in range(n)]
    data.sort(key=lambda x:x[-1])
    kruskal()
        

---

결과

입력 조건이 지금까지 풀었던 문제들과 달랐다. 여러 테스트 케이스로 나눠져 있고, 0 0을 만나면 종료하는 조건이므로 무한루프를 돌고 0 0을 만나면 break 하도록 코드를 짜야한다.