[🥇4 / 백준 6497 / 파이썬] 전력난

 

6497번: 전력난

 

문제

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

그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으로 서로를 왕래할 수 있어야 한다.

위 조건을 지키면서 절약할 수 있는 최대 액수를 구하시오.

입력

입력은 여러 개의 테스트 케이스로 구분되어 있다.

각 테스트 케이스의 첫째 줄에는 집의 수 m과 길의 수 n이 주어진다. (1 ≤ m ≤ 200000, m-1 ≤ n ≤ 200000)

이어서 n개의 줄에 각 길에 대한 정보 x, y, z가 주어지는데, 이는 x번 집과 y번 집 사이에 양방향 도로가 있으며 그 거리가 z미터라는 뜻이다. (0 ≤ x, y < m, x ≠ y)

도시는 항상 연결 그래프의 형태이고(즉, 어떤 두 집을 골라도 서로 왕래할 수 있는 경로가 있다), 도시상의 모든 길의 거리 합은 2³¹미터보다 작다.

입력의 끝에서는 첫 줄에 0이 2개 주어진다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 절약할 수 있는 최대 비용을 출력한다.

 

예제 입력 7 11 0 1 7 0 3 5 1 2 8 1 3 9 1 4 7 2 4 5 3 4 15 3 5 6 4 5 8 4 6 9 5 6 11 0 0

예제 출력 51

 

풀이

 

최소 신장 트리 문제로, 프림 혹은 크루스칼 아무거나 사용해도 풀린다.

필자는 프림으로 해결하여서 해당 코드를 첨부한다.

 

문제에서 주어지는 n개의 간선 만큼 가로등이 깔려있다고 생각하도록 하자.

이 중, 모든 집을 최소한의 가중치로 연결하고 나머지 가로등(간선)의 전원을 차단할 것이다.

그리고, 모든 가로등을 켰을 때와 비교하여 절약할 수 있는 비용을 출력하면 된다.

 

주의할 것은, 최소 신장 트리의 총 가중치를 출력하는 것이 아닌 '절약할 수 있는 최대 비용'을 출력해야 한다는 점이다.

따라서 모든간선의 합에서 최소 신장 트리의 가중치를 제외한 것을 출력하도록 하자.

(예제의 경우 총 간선의 길이 = 90, 최소 신장 트리 = 39, 절약할 수 있는 비용 = 51)

 

import sys, heapq
input = sys.stdin.readline

while True:
    v,e = map(int,input().split())
    if v==0 and e==0:
        break
    
    visited = [False] * v
    edges = [[] for _ in range(v)]
    ans = 0
    
    total = 0 # 모든 간선의 합
    for _ in range(e):
        x,y,z = map(int,input().split())
        edges[x].append((z,y))
        edges[y].append((z,x)) # 양방향 그래프이므로 반대도 고려한다
        total += z
    
    hq = [i for i in edges[0]]
    heapq.heapify(hq) # 힙 정렬 수행
    visited[0] = True # 프림 알고리즘 최초 시작 정점을 0번으로 정했다.
    
    while hq:
        cur_w, cur_v = heapq.heappop(hq)
        if visited[cur_v]:
            continue
        visited[cur_v] = True
        
        ans += cur_w
        for i in edges[cur_v]:
            heapq.heappush(hq, i)
    print(total - ans)