[Python] 백준 6497번 - 전력난

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

6497번: 전력난

 

스터디할 때는 크루스칼 어려웠는데 지금은 할 만하다.

문제 해결에 필요한 로직대로만 조금 수정하고 find, union 함수 사용하면 돼서 금방 익숙해진 것 같다.

MST 어려워서 겁먹었었는데 이제는 좀 더 마음 놓고 시도해도 될 것 같다.

 

import sys
input = sys.stdin.readline

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

def union(a, b):
    a = find(a)
    b = find(b)
    if a > b:
        parent[a] = b
    else:
        parent[b] = a

while True:
    m, n = map(int, input().split())
    if m == 0 and n == 0:
        break
    edge = []
    parent = [i for i in range(m+1)]
    ans = 0

    for i in range(n):
        x, y, z = map(int, input().split())
        edge.append((x, y, z)) #z: 가중치

    edge.sort(key=lambda x:x[2])

    for i in edge:
        x, y, z = i
        if find(x) != find(y):
            union(x, y)
        else:
            ans += z
    print(ans)

런타임에러 왜 났었더라... 기억 안 난다..