[백준] 6497번 전력난 (파이썬)

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

난이도: GOLD IV

문제해결 아이디어

• 각 노드가 연결되어 있으며 가중치 값이 최소화 되는 MST 이다
• 가중치를 기준으로 오름차순으로 정렬하여 union, find를 진행한다.

소스코드

import sys
input = sys.stdin.readline

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])

    return parent[x]

def union(x,y):
    x,y = find(x), find(y)
    if x < y:
        parent[y] = x
    else:
        parent[x] = y

while True:
    n,m = map(int, input().split())
    if n == 0 and m == 0:
        break
    graph = []

    for _ in range(m):
        a,b,c = map(int, input().split())
        graph.append((a,b,c))
    
    parent = [i for i in range(n)]
    
    graph.sort(key=lambda x: x[2]) # 가중치를 기준으로 오름차순 정렬
    
    answer = 0
    
    for a,b,c in graph:
        if find(a) != find(b): # 부모노드가 다르면 합친다
            union(a,b)
        else:
            answer += c # 이미 연결되어 있으면 가중치를 더함
            
    print(answer)
    ```