백준 6497번 전력난 문제 풀이

문제 설명

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

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

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

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

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

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

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

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

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

문제 풀이

크루스칼 알고리즘을 이용해서 최소 신장 트리를 만드는 문제이다.

edges 배열을 선언하여 모든 edges를 저장한 후, 가중치를 기반으로 정렬한다.

비용이 적은 도로부터 연결(Union)하면서 모든 집이 연결되게 만들면 된다.

만약 간선의 두 끝이 Root 노드가 같다면 같은 집합에 속하여 이미 이동할 수 있다는 뜻이므로 넘어간다. 그렇지 않으면 두 집합을 합친다(Union).

최종적으로 절약할 수 있는 최대 금액을 출력하는 것 이므로, 모든 간선의 가중치에서 최소 신장 트리의 가중치를 빼주면 된다.

입력이 조금 특이해서 애먹었는다. 테스트케이스가 한꺼번에 주어지는 것이니, N==0 and M==0 일때 까지 하나의 테스트케이스에 대한 입력을 받고 출력을 해야한다.

입출력 예시

입력 예시 1

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

출력 예시 1

51

CODE

import heapq
import sys
input = sys.stdin.readline

def find_parent(parent, x):
    if x != parent[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)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

if __name__ == "__main__":
    
    while True:
        N, M = map(int, input().split())
        if N == 0 and M == 0:
            break
        
        parent = [i for i in range(N)]
        edges = []
        answer = 0
        
        for _ in range(M):
            v1, v2, W = map(int, input().split())
            heapq.heappush(edges, (W, v1, v2))
            answer += W
        
        while edges:
            W, v1, v2 = heapq.heappop(edges)
            
            if find_parent(parent, v1) == find_parent(parent, v2): # 간선의 두 노드가 이미 같은 집합에 속해 있다면
                continue
            else:
                union_parent(parent, v1, v2)
                answer -= W
        
        print(answer)

시간 복잡도

• M개의 각선에 대하여 힙에 추가하는 데에 각각 $O(logM)$의 시간이 걸리므로 최종적으로 $O(MlogM)$ 시간이 걸린다.
• 크루스칼 알고리즘은 힙에서 꺼내는 데에 $O(logM)$의 시간이 들고, Union-Find 알고리즘을 수행하는 데에 거의 상수시간에 가깝다.