BOJ - 4485 - 녹색 옷 입은 애가 젤다지?

import sys
from heapq import heappush, heappop

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

def Dijkstra(graph, N):
    heap = []
    distance = [[INF] * N for _ in range(N)]

    heappush(heap, (graph[0][0], 0, 0))
    distance[0][0] = 0

    while heap:
        weight, x, y = heappop(heap)
        if x == N-1 and y == N-1:
            return weight

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

            if 0 <= nx < N and 0 <= ny < N:
                w = weight + graph[nx][ny]
                if w < distance[nx][ny]:
                    distance[nx][ny] = w
                    heappush(heap, (w, nx, ny))

def solution():
    cnt = 1
    while True:
        N = int(input())
        if N == 0:
            break
        graph = []
        for _ in range(N):
            graph.append(list(map(int, sys.stdin.readline().split())))

        print("Problem {0}: {1}".format(
            cnt, Dijkstra(graph, N)
        ))
        cnt += 1
solution()

https://www.acmicpc.net/problem/4485