[백준 6497 파이썬] 전력난 (골드 4, MST)

알고리즘 유형 : 최소 신장 트리
풀이 참고 없이 스스로 풀었나요? : O

https://www.acmicpc.net/problem/6497

소스 코드(파이썬)

import sys
input = sys.stdin.readline

def find(x):
    if parent[x] < 0:
        return x
    
    parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    root_a = find(a)
    root_b = find(b)
    
    if root_a == root_b:
        return False
    
    if parent[root_a] < parent[root_b]:
        parent[root_b] = root_a
    elif parent[root_a] > parent[root_b]:
        parent[root_a] = root_b
    else:
        parent[root_a] = root_b
        parent[root_b] -= 1
    
    return True

m, n = map(int, input().split())

while (m, n) != (0, 0):
    edges = []
    cost_max = 0
    
    for _ in range(n):
        x, y, z = map(int, input().split())
        edges.append((z, x, y))
        
        cost_max += z
    
    edges.sort()
    
    parent = [-1]*m
    cnt_linked = 0
    cost = 0
    
    for z, x, y in edges:
        if cnt_linked == m-1:
            break
        
        if union(x, y):
            cost += z
            cnt_linked += 1
    
    print(cost_max - cost)
    
    m, n = map(int, input().split())

풀이 요약

1. 모든 집이 서로 왕래가 가능해야한다는 것은 곧 모든 집(노드)이 연결되어있어야 한다는 것과 같다. 집을 잇는 길이 간선인데, 도로 길이가 간선의 가중치이다. 길에는 가로등이 하나씩 있다.

   길의 가로등을 키는 것을 길을 선택하는 것으로 생각하자. 이 때, 임의의 두 집 사이에 반드시 경로가 존재하도록 길을 선택하되, 그 가중치가 최소가 되어야한다. 전형적인 최소 신장 트리 문제이다.

   다만 조건을 만족할 때의 가중치의 합이 정답이 아니고, 원래 모든 길의 가로등을 켰을 때와 대비해서 어느 정도 절약되었는지를 출력해야하므로, 모든 간선의 가중치의 합에서 최소 신장 트리의 가중치 합을 빼면 절약값을 알 수 있다.

2. 이 풀이에서는 크루스칼을 사용했다. 간선을 가중치 기준으로 정렬한 후 그리디하게 하나씩 union find로 합집합 트리를 만들어서 최소 신장 트리를 구하고, 그 때의 가중치 합을 활용해 답을 구해준다,

배운 점, 어려웠던 점

• 조건을 보고 최소 신장 트리를 떠올리기만 하면 되는, 구현은 쉬운 문제였다.