백준13549: 숨바꼭질 3 - 최단 거리, 다익스트라(Python/파이썬)

import sys
import heapq
input = sys.stdin.readline

def dijkstra(start, goal):
    dist = [float('inf')] * 100001
    pq = [(0, start)]
    dist[start] = 0
    turn = 0
    while pq:
        time, now = heapq.heappop(pq)
        if dist[now] < time:
            continue
        d = [-1, 1, now]
        t = [1, 1, 0]
        for i in range(3):
            next = now + d[i]
            dis = time + t[i]
            if 0 <= next < 100001 and dist[next] > dis:
                dist[next] = dis
                heapq.heappush(pq, (dis, next))

    return dist[goal]

N, K = map(int, input().split())
print(dijkstra(N, K))

원래 중간에 디버깅 코드가 있었는데 pq = [(1,4), (0, 10), (1,6)] 인 상황에서 (1,4)를 제일 먼저 방문하길래 이유를 찾고자 gpt를 닦달했다. 알고보니까 삽입연산 시 heqppush가 아니라 리스트에 pq.append로 냅다 넣어서 트리 구조가 꼬인 것이었음. 근데 얻어 걸려서 그게 올바른 코드보다 시간을 단축해주긴 했다...

우선순위큐 사용 시 다익스트라 시간복잡도

노드의 수 V, 간선의 수 E인 그래프의 시간복잡도
O((E + V) log V)