BOJ 6497 - 전력난

문제

백준 온라인 저지 - 6497번

풀이 과정

모든 도시를 최소 비용으로 연결하는 방법을 찾는 문제입니다.
크루스칼 알고리즘 을 활용해서 MST 를 구축하고 절약 가능한 비용을 계산하면 됩니다.

코드

import sys
import heapq

sys.setrecursionlimit(10**6)

parent = []


def union(u, v):
    u, v = find(u), find(v)
    if u == v:
        return

    parent[u] = v


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

    parent[u] = find(parent[u])
    return parent[u]


def solution(N, edges):
    ret = 0

    for _ in range(N):
        cost, src, dst = heapq.heappop(edges)
        if find(src) != find(dst):
            ret += cost
            union(src, dst)

    return ret


if __name__ == '__main__':
    while 1:
        M, N = list(map(int, sys.stdin.readline().split()))
        if M == 0:
            break

        total = 0
        edges = []
        for _ in range(N):
            src, dst, cost = list(map(int, sys.stdin.readline().split()))
            edges.append([cost, src, dst])
            total += cost

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

        heapq.heapify(edges)
        answer = total - solution(N, edges)
        print(answer)