[백준 1647번] 도시 분할 계획 (Python3)

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가 더 느리고.. 프로그래밍의 세계는 참 오묘한것 같다.

 

오늘의 교훈) 크루스칼 알고리즘은 리스트로 구현하자