다익스트라 공부를 시작하고 얼마 되지 않아 이 문제를 맞닥뜨리면 당황할 수도 있다.
2차원이기 때문. 자세히 알아보자.

BOJ 4485 - 녹색 옷 입은 애가 젤다지? 링크
(2022.09.29 기준 G4)
(치팅하는 애가 너지?)

문제

N * N 크기의 동굴이 있고 각 칸에는 소지한 금액이 감소하는 '도둑루피'가 있다.
(0, 0)에서 시작하여 (N - 1, N - 1)까지 이동할 때 잃는 최소 금액

알고리즘

각 칸마다 가중치가 정해져 있다.
이 가중치가 최소가 되게끔 목적지까지 이동해야 하므로, 다익스트라

풀이

다익스트라를 많이 접하지 못했다면 아마 이런 유형은 처음 볼 것이다.
행렬에서 BFS나 DFS 탐색처럼 진행해야 하기 때문. 하지만 겁먹지 말자.
그냥 distance를 2차원 배열로 선언하여 각 칸마다의 최단 거리를 넣는다고 생각하고, 시작점에서 BFS 탐색하듯이 상하좌우로 1칸씩 움직이면서 만약에 최단 거리가 갱신이 된다면, 거리를 갱신하고 이동하면 된다.

사실 너무 간단한 문제라서 풀이가 짧다.
코드에 주석을 달아놓았으니 참고하자.

코드

import sys; input = sys.stdin.readline
import heapq
from math import inf

def solve():
    N = int(input())
    if not N: # 0이면 프로그램 종료
        exit()
    matrix = [list(map(int, input().split())) for _ in range(N)] # 동굴

    # 각 칸마다 잃는 금액의 최소를 저장하면서 진행 (다익스트라)
    distance = [[inf] * N for _ in range(N)]
    queue = [[matrix[0][0], 0, 0]] # (0, 0)에서 시작하므로 힙에 넣자.
    distance[0][0] = matrix[0][0] # (0, 0)에서의 잃는 금액을 갱신하고 다익스트라 시작

    # 다익스트라
    while queue:
        lose, n, m = heapq.heappop(queue) # 잃는 금액, 좌표 n, m
        # 각 위치의 잃는 최소 금액보다 lose보다 작으면
        # 이미 최소 금액으로 거리 갱신이 되었다는 의미이므로 lose로 거리 갱신할 필요가 없다.
        if distance[n][m] < lose:
            continue
        for nn, mm in [(n - 1, m), (n + 1, m), (n, m - 1), (n, m + 1)]: # 상하좌우
            # 다음 위치가 범위 안이어야 하고, 그 위치에 저장된 거리보다 지금 거리 + 각 칸의 가중치가 작으면 갱신
            if 0 <= nn < N and 0 <= mm < N and distance[nn][mm] > distance[n][m] + matrix[nn][mm]:
                distance[nn][mm] = distance[n][m] + matrix[nn][mm]
                heapq.heappush(queue, [distance[nn][mm], nn, mm])
    return distance[N - 1][N - 1]

p = 1 # 문제 번호
while True:
    print('Problem %d: %d' % (p, solve()))
    p += 1

여담

한달 전에 젤다 야숨을 아주 기대에 차서 샀었다. 그런데.. 1시간 하고 끄고 그 후로 한 번도 안들어감... 진짜 내 스타일 아닌 듯. (돈 아까워 ㅠㅠ)
원신도 얼마 안하고 접고 그랬는데, 아마 이런 게임은 내 스타일이 아닌 것 같다.