백준 4485: 녹색 옷 입은 애가 젤다지? - 다익스트라, 델타 탐색(Python/파이썬)

그래프 탐색 대신 2차원 배열에 델타 탐색 사용하여 다익스트라 구현.
다익스트라인 거 알면 쉽게 풀리는데 지금 내가 알고리즘 분류에서 다익스트라만 골라서 푸는 중이라 쉽게 푼 거고 그냥 문제만 봤으면 한참 고민했을 것 같다.

import sys
import heapq

input = sys.stdin.readline

def dijkstra(graph, n):
    distance = list([float('inf')] * n for _ in range(n))
    q = []
    heapq.heappush(q, (graph[0][0], 0, 0))
    distance[0][0] = graph[0][0]

    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]
    while q:
        cost, x, y = heapq.heappop(q)
        if distance[x][y] < cost:
            continue

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n:
                total_cost = cost + graph[nx][ny]
                if distance[nx][ny] > total_cost:
                    distance[nx][ny] = total_cost
                    heapq.heappush(q, (total_cost, nx, ny))

    return distance[n-1][n-1]

tc = 1
while True:
    N = int(input())
    if N == 0:
        break
    board = list(list(map(int, input().split())) for _ in range(N))
    ans = dijkstra(board, N)
    print(f'Problem {tc}: {ans}')
    tc += 1