[BOJ 1197] 최소 스패닝 트리 (Python3)

https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

import heapq

q=[]
V, E=map(int, input().split())
parents=[0]
cnt=0
ans=0

def find(a):
    if parents[a]==a:
        return a
    parents[a]=find(parents[a])
    return parents[a]

def union(a, b):
    pa=find(a)
    pb=find(b)
    if pa!=pb:
        parents[pa]=pb

for i in range(E):
    A,B,C=map(int, input().split())
    heapq.heappush(q, (C,A,B))
for i in range(1,V+1):
    parents.append(i)

while True:
    if cnt==V-1:
        break
    e=heapq.heappop(q)
    pa=find(e[1])
    pb=find(e[2])
    if pa!=pb:
        union(pa,pb)
        cnt+=1
        ans+=e[0]

print(ans)

확실히 Python이 코드는 간단하나 시간이 오래 걸린다..

게다가 우선순위 큐 라이브러리인 PriorityQueue는 "동기화" 기능이 있어서 속도가 느리다.

그때는 heapq를 써주면 된다.

 

크루스칼 알고리즘으로 MST 를 구현하는 문제.