백준 6497 : 전력난 (Python)

본문 링크

📌 크루스칼 알고리즘

import sys
input=sys.stdin.readline

def Find(x):

    if x!=disjoint[x]:
        disjoint[x]=Find(disjoint[x])
    return disjoint[x]

while True:

    M,N=map(int,input().split())

    if [N,M]==[0,0]:
        break

    disjoint=[ _ for _ in range(M+1) ]
    total=0

    MST=[]
    for i in range(N):
        x,y,z=map(int,input().split())
        total+=z
        MST.append((x,y,z))

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

    value=0
    for x,y,z in MST:

        x=Find(x)
        y=Find(y)

        if x!=y:
            if x>y:
                disjoint[x]=y
            else:
                disjoint[y]=x
            value+=z

    print(total - value)

📌 프림 알고리즘

import sys,heapq
input=sys.stdin.readline

while True:

    M,N=map(int,input().split())

    if [M,N]==[0,0]:
        break

    Tree=[ [] for _ in range(M+1) ]
    visit=[False]*(M+1)

    total=0
    for i in range(N):
        x,y,z=map(int,input().split())
        total+=z

        Tree[x].append((z,y)) #거리를 먼저 추가하고 좌표값 추가.
        Tree[y].append((z,x))

    heap=[(0,0)]

    check_total=0

    while heap:

        value,node=heapq.heappop(heap)

        if not visit[node]:
            visit[node]=True
            check_total+=value

            for i,j in Tree[node]:
                heapq.heappush(heap,(i,j))

    print(total-check_total)

📌 어떻게 접근할 것인가?

최소 스패닝 이론 문제입니다. 그냥 크루스칼 알고리즘과 프림 알고리즘을 구현한 다음에
문제에서 주어지는 전체 가중치의 값 - 최소 가중치의 값 을 구하면 절약할 수 있는 값이 나옵니다.