import sys
input = sys.stdin.readline
from heapq import heappush,heappop
def findparent(x):
if parent[x] == x:
return x
parent[x] = findparent(parent[x])
return parent[x]
V,E = map(int,input().split())
hq = []
for i in range(E):
x1,x2,w = map(int,input().split())
heappush(hq,(w,x1,x2))
parent = {i:i for i in range(1,V+1)}
result = 0
while hq:
w,x1,x2 = heappop(hq)
if findparent(x1) == findparent(x2):
continue
parent[findparent(x1)] = findparent(x2)
result += w
maxw = w
print(result-maxw)
최소 신장 트리를 풀고나면 1초만에 풀 수 있는 문제
최소신장 트리에서 maxw만 지정해주고, 최종 결과에서 빼면 된다.
최소신장트리 알고리즘에서 딱 한줄 한단어 추가된듯
그런데 시간이 조금 오래 걸리는 것 같아서 다른 사람들 풀이를 참고하니 보통 크루스칼 알고리즘은 heapq로 구현하지 않고 리스트로 구현한다음 sort하는 방식을 사용한다는 것을 알게되었다.
리스트로 구현한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
def findparent(x):
if parent[x] == x:
return x
parent[x] = findparent(parent[x])
return parent[x]
V,E = map(int,input().split())
graph = []
for i in range(E):
x1,x2,w = map(int,input().split())
graph.append((w,x1,x2))
parent = {i:i for i in range(1,V+1)}
graph.sort()
result = 0
for w,x1,x2 in graph:
if findparent(x1) == findparent(x2):
continue
parent[findparent(x1)] = findparent(x2)
result += w
maxw = w
print(result-maxw)
리스트로 구현하니 아주 약간 시간이 개선되었다.
여담으로 이 문제는 python3로 제출할때보다 오히려 pypy3로 제출했을때 더 시간이 오래 걸리는 결과를 보여줬는데, 어떤 문제는 pypy가 2~30배 더 빠르기도 하고 어떤 문제는 오히려 pypy가 더 느리고.. 프로그래밍의 세계는 참 오묘한것 같다.
오늘의 교훈) 크루스칼 알고리즘은 리스트로 구현하자