백준 4485 녹색 옷 입은 애가 젤다지?

import heapq
INF = int(1e9)

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
i = 1
while True:
    n = int(input())

    if n == 0:
        break

    g = [list(map(int, input().split())) for _ in range(n)]
    d = [[INF] * n for _ in range(n)]
    q = []
    
    heapq.heappush(q, (g[0][0], 0, 0))
    d[0][0] = g[0][0]

    while q:
        dist, now_x, now_y = heapq.heappop(q)
        if d[now_x][now_y] < dist:
            continue
        for dir in range(4):
            nx, ny = now_x + dx[dir], now_y + dy[dir]
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            cost = g[nx][ny] + dist
            if cost < d[nx][ny]:
                d[nx][ny] = cost
                heapq.heappush(q, (cost, nx, ny))
    print(f"Problem {i}: {d[n-1][n-1]}")
    i += 1

다익스트라 + 이차원 (한곳 -> n곳 최단거리니까 쓸 수 있음)
.. 변수 중복해서 쓰지 말자