백준 1197 : 최소 스패닝 트리 (Python)

본문 링크

📌 크루스칼 알고리즘

import sys
input=sys.stdin.readline

def Find(x):

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


V,E=map(int,input().split())

disjoint=[ i for i in range(V+1) ]

MST=[]
for i in range(E):
    MST.append(list(map(int,input().split())))

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

value=0

for U,V,K in MST:

    U=Find(U)
    V=Find(V)

    if U!=V:
        if U>V:
            disjoint[U]=V
        else:
            disjoint[V]=U
        value+=K

print(value)

📌 프림 알고리즘

import sys,heapq
input=sys.stdin.readline

V,E=map(int,input().split())

visit=[False]*(V+1)

MST=[ [] for _ in range(V+1) ]
heap=[ [0,1] ]

for i in range(E):
    s,e,w=map(int,input().split())

    MST[s].append([w,e])
    MST[e].append([w,s])


value=0

while heap:

    w,s=heapq.heappop(heap)

    if not visit[s]:
        visit[s]=True
        value+=w

        for i in MST[s]:
            heapq.heappush(heap,i)

print(value)

📌 어떻게 접근할 것인가?

최소 스패닝 트리 기초 문제입니다.

크리스칼 , 프림 알고리즘을 그대로 구현해주면 됩니다.

최소 스패닝 이론에 관한 글은 제가 쓴 블로그 를 참조하셔도 좋습니다.