백준 #6497 전력난

코드

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

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

while True:
    m, n = map(int, input().split())
    if m == 0:
        break
    graph = []
    total = 0
    for _ in range(n):
        x, y, cost = map(int, input().split())
        graph.append([cost, x, y])
        total += cost

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

    graph.sort()

    temp = 0
    for cost, start, end in graph:
        start = find(start)
        end = find(end)
        if start != end:
            if start < end:
                parent[end] = start
            else:
                parent[start] = end
            temp += cost
    print(total - temp)

풀이

유니온 파인드에 대한 감을 잃지 않기 위해 풀어보았다.

문제 유형은 최소 스패닝 트리이고 비용이 낮은 순으로 정렬 후 두 점이 연결되어 있지 않다면

두 점을 연결해주면서 비용을 더해준다.

입력 방식이 여러개의 테스트케이스가 존재 했던 것만 빼면 특별한 점은 없었다!