[Python] 백준 4485. 녹색옷 (Dijkstra)

Point

• heapq(우선순위큐)를 이용해서 개선된 다익스트라 알고리즘 사용해야 함.
  (다익스트라 알고리즘을 그대로 사용하면 시간초과 발생)

이유

우선순위 큐는 다익스트라 알고리즘의 병목현상을 개선함.

• 병목현상이란 기존 다익스트라 알고리즘의 대표적 문제점으로, 시작 노드와 가장 거리가 짧은 최단 거리 노드를 찾을 때 매번 선형탐색을 수행함으로써 생기는 비효율적인 상황을 의미함.
• 우선순위 큐는 시작 노드와 가장 거리가 짧은 최단 거리 노드를 찾는 시간 복잡도를
  O(N) 아닌 O(logN) 으로 줄임으로써 알고리즘의 효율성을 매우 개선할 수 있음
• 이런 다음 최단 거리 노드 찾는 것을 모든 노드에 대해 반복하므로 개선된 다익스트라 시간복잡도는 O(ElogN).

코드

import sys
from math import inf
from heapq import heappush, heappop

input = sys.stdin.readline

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def dijkstra():
    q = []
    dist[0][0] = graph[0][0]  # 시작노드의 비용 설정
    heappush(q, (dist[0][0], [0, 0]))  # 시작 노드부터의 x 노드까지의 비용, x의 좌표

    while q:
        d, node = heappop(q)
        x, y = node
        if dist[x][y] < d:  # 큐에서 뽑아낸 거리가 이미 갱신된 거리보다 큰 경우 이미 방문한 셈이므로 무시
            continue
        for i, j in zip(dx, dy):
            n_x, n_y = x + i, y + j
            if 0 <= n_x < N and 0 <= n_y < N:  # in range check
                cost = d + graph[n_x][n_y]  # 시작->현재 노드까지의 비용 + 현재노드->다음노드까지의 비용
                if cost < dist[n_x][n_y]:  # 시작->다음노드까지의 비용보다 적을 경우
                    dist[n_x][n_y] = cost
                    heappush(q, (cost, [n_x, n_y]))
    return dist[N - 1][N - 1]


if __name__ == '__main__':
    caseNum = 0

    while True:
        caseNum += 1
        N = int(input())
        if N == 0:
            exit(0)
        graph = [list(map(int, input().split())) for _ in range(N)]
        dist = [[inf for _ in range(N)] for _ in range(N)]

        print("Problem {}: {}".format(caseNum, dijkstra()))