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

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

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

---

풀이

방향성 생각

• MST를 만들어서 필요없는 간선의 cost가 얼마인지 구하자.

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

def find(a):
    if parent[a] != a:
        parent[a] = find(parent[a])
    return parent[a]

def union(a,b):
    parent[max(a,b)] = min(a,b)

while True:

    # TEST CASE : 입력 -> 간선
    N,K = map(int,input().split())
    if (N,K) == (0,0):
        break

    # edges를 내림차순으로 정렬
    edges = [tuple(map(int,input().split())) for _ in range(K)]
    edges.sort(key = lambda x:-x[-1])
    parent = [i for i in range(N)]

    # 연결하지 않는 간선 / 연결한 간선 코스트 세주기.
    total,cnt = 0,0
    while edges:
        a,b,cost = edges.pop()
        pa,pb = find(a),find(b)
        total += cost
        if pa != pb:
            union(pa,pb)
            cnt += cost
    print(total-cnt)

코멘트

• 기본 MST 문제