[파이썬, Python] 백준 6497번 : 전력난

백준 6497번 : 전력난

(문제 바로가기)

 

 

내 코드

import sys

input = sys.stdin.readline


def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b


while True:
    m, n = map(int, input().split())  # m: 집의 수, n: 길의 수
    if m == 0 and n == 0:
        break

    parent = [i for i in range(m)]

    edges = [tuple(map(int, input().split())) for _ in range(n)]  # 길 정보
    edges.sort(key=lambda x: x[2])  # 길의 미터수를 기준으로 오름차순 정렬

    result = 0
    for x, y, z in edges:
        if find_parent(parent, x) != find_parent(parent, y):  # 이어지지 않은 길이라면
            union(parent, x, y)
        else:  # 절약할 수 있는 길이라면
            result += z
    print(result)