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

이전글

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

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

문제

• 백준 1753번

최종 코드

• Python3에서만 동작

import sys
import math
from queue import PriorityQueue
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 = PriorityQueue()
que.put((distance[k], k))

while not que.empty():
    now = que.get()[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
            que.put((distance[node], node))

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

    print(distance[i])

 

풀이 과정

---

• 이전 글에서 제출했던 코드의 경우 시간 초과가 나는 경우가 있었기 때문에 어떻게 하면 시간을 줄일 수 있을지 고민했다
• 이전 코드에서 find_min_distance_node() 함수를 통해 선택하지 않은 노드 중 최소 거리 리스트에서 최솟값을 선택했는데 해당 부분에서 모든 노드를 선택하여 최소 거리를 찾는 동안 반복문을 돌며 최솟값을 찾기 때문인 것 같다고 생각했다!
  • 대충 시간복잡도가 O(VE) 정도 되는 것 같다!
• 다익스트라 알고리즘 실행 중 모든 노드를 선택해야하는 것은 필수불가결하기 때문에 최단 거리 리스트에서 최솟값을 찾는 작업에서 시간을 줄여보려 고민했다
• 고민하던 중 Heap을 이용하여 구현한 PriorityQueue(우선순위 큐)를 떠올려서 사용하였다
  • 파이썬의 PriorityQueue는 기본적으로 정렬된 상태를 유지하며 원소를 반환할때 O(logN)의 시간복잡도를 가지기 때문에 조금 더 시간을 단축할 수 있다고 생각했다!
  • 이때 PriorityQueue를 사용해서 대충 O(VlogE) 정도로 시간 복잡도를 줄였다고 생각한다
• 따라서 기존에 함수로 처리하던 부분을 PriorityQueue 자료구조를 이용하여 처리하는 방식으로 변경하였고, 최단 거리 리스트에서 갱신이 발생할 때 해당 에지의 정보를 PriorityQueue에 저장해서 정렬되도록 하였다
• 로컬 PC에서 테스트를 먼저 해보고 잘 동작되어서 백준 사이트에 제출을 했지만.. 이유는 모르겠지만 pypy3로 제출했을 때 런타임 에러가 발생했다...
• 혹여 코드를 잘못 쓴 곳이 있나 확인도하고 단순 에러인가 싶어 여러번 제출했지만 결과는 똑같았다...
• 마지막으로 혹시나 하는 마음에 Python3로 설정하고 제출하니 정답이라고 나왔다...
  • 아직까지는 이유를 정확히 모르겠지만 좀 더 찾아보고 pypy3에서도 동작하는 코드를 만들어 봐야겠다..
  • pypy3에서도 동작하는 코드가 궁금하다면 아래 글로!

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

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

 

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