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

과정

• 다익스트라
• 가중치가 최소가 되도록 도착지에 도달해야한다.

import sys
input = sys.stdin.readline

import heapq

INF = 1e9

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

def dijkstra(x, y):
    # init
    q = []
    heapq.heappush(q, (map_lst[y][x], x, y))
    dp[y][x] = map_lst[y][x]

    # q
    while q:
        rupee, x, y = heapq.heappop(q)
        # 이미 처리한 곳이면 무시
        if dp[y][x] < rupee:
            continue
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 인덱스 벗어난 경우
            if nx < 0 or nx >= N or ny<0 or ny >= N:
                continue

            cost = map_lst[ny][nx] + rupee
            if dp[ny][nx] > cost:
                dp[ny][nx] = cost
                heapq.heappush(q, (cost, nx, ny))

i = 1
while True:
    N = int(input())
    if N == 0:
        break

    map_lst = [list(map(int, input().split())) for _ in range(N)]
    dp = [[INF for _ in range(N)] for _ in range(N)]

    dijkstra(0, 0)
    print(f'Problem {i}: {dp[-1][-1]}')
    i += 1