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

문제 내용

 

간단한 최소 신장 트리 문제.

별다른 설명을 할 게 없다.

크루스칼, 프림 등등 최소 신장 트리 알고리즘 중 하나 선택해서 적용하면 바로 풀린다.

나는 크루스칼을 사용했다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

v,e=map(int,input().split())
L=[]
cycle=[i for i in range(v+1)]
ans=0
n=0
for i in range(e):
    a,b,c=map(int,input().split())
    heapq.heappush(L,[c,min(a,b),max(a,b)])
    
def find(u):
    if u!=cycle[u]:
        cycle[u]=find(cycle[u])
    return cycle[u]

def union(u,v):
    u=find(u)
    v=find(v)
    cycle[v]=cycle[u]

while n<v-1:
    c,a,b=heapq.heappop(L)
    if find(a)!=find(b):
        ans+=c
        union(a,b)
        n+=1
print(ans)

크루스칼을 구현 못해서 좀 헤맸다.