[Python] 백준 - 1753번 최단경로(3)

이전글

[Python] 백준 - 1753번 최단경로(2)

[Python] 백준 - 1753 최단경로(2)

문제

• 백준 1753번

최종 코드

• pypy3, Python3 모두 동작!

import sys
import math
import heapq
input = sys.stdin.readline

V, E = map(int, input().split())
visited = [False] * (V + 1)
distance = [math.inf] * (V + 1)
g = [[] for _ in range(V + 1)]

k = int(input())
distance[k] = 0

for _ in range(E):
    u, v, w = map(int, input().split())
    g[u].append((v, w))

que = []
heapq.heapify(que)
heapq.heappush(que, (distance[k], k))

while que:
    now = heapq.heappop(que)[1]

    if visited[now]:
        continue

    visited[now] = True

    for t in g[now]:
        node, value = t[0], t[1]

        if distance[node] > distance[now] + value:
            distance[node] = distance[now] + value
            heapq.heappush(que, (distance[node], node))

for i in range(1, V + 1):
    if distance[i] == math.inf:
        print("INF")
        continue

    print(distance[i])

 

풀이과정

---

• 로컬 PC에서 pypy3 환경으로 테스트를 했을때는 잘 동작했던 코드가 백준에 제출했을때는 런타임 에러가 발생하였다
• 찾아본 결과 백준에서 pypy3 언어로 제출할 때 PriorityQueue 모듈 사용이 막혀있는 것 같다
• 따라서 이전 코드에서 PriorityQueue를 사용했던 부분을 heapq를 이용하여 수정하였고 pypy3와 Python3로 제출했을 때 모두 정답으로 처리됐다! 
  • PriorityQueue의 경우 heapq를 이용하여 만들어져서 그런지 코드를 변환하기 수월했다!
  • 추가로 코드를 변환하면서 두 모듈의 차이점이 무엇인지 궁금해져 학습해봐야겠다!

틀린 부분 또는 궁금한 점은 댓글로 남겨주세요! 항상 환영합니다!