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

1. 문제

4485번: 녹색 옷 입은 애가 젤다지?

2. 개요

젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 ‘도둑루피’라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다!

젤다는 현재 동굴의 0,0에 위치해 있다. 이 동굴의 모든 칸에는 도둑루피가 있고 칸을 지날 때마다 도둑루피의 크기만큼 루피를 잃게 된다.

젤다가 동굴의 N-1, N-1까지 가기 위해 잃을 수 밖에 없는 최소 루피를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

다익스트라를 이용한다.

힙큐, 우선순위 큐에 (잃은 루피, y좌표, x좌표)를 원소로 넣으면서 항상 잃은 루피가 최소인 경우를 먼저 뽑아올 수 있도록 하면서 모든 좌표를 탐색한다.

칸을 방문할 때마다 visited의 값을 최솟값으로 갱신해나가며 방문처리한다.

탐색이 끝난 후 마지막 칸의 값을 출력한다.

3-2. Python

import sys
import heapq

dirY, dirX = [-1, 0, 1, 0], [0, -1, 0, 1]
idx = 1

while True:
    N = int(sys.stdin.readline())

    if N == 0:
        break

    board = []
    visited = [[10000 for i in range(N)] for j in range(N)]

    for i in range(N):
        board.append(list(map(int, sys.stdin.readline().split())))

    q = [[board[0][0], 0, 0]]
    visited[0][0] = board[0][0]

    while q:
        now = heapq.heappop(q)
        nowtime, nowY, nowX = now[0], now[1], now[2]

        for i in range(4):
            nextY, nextX = nowY + dirY[i], nowX + dirX[i]
            
            if nextY < 0 or nextY >= N or nextX < 0 or nextX >= N:
                continue

            if visited[nextY][nextX] != 10000:
                continue

            nexttime = nowtime + board[nextY][nextX]
            visited[nextY][nextX] = nexttime
            heapq.heappush(q, [nexttime, nextY, nextX])

    print("Problem %s: %d" %(idx, visited[-1][-1]))
    idx += 1

3-3. C#

namespace boj_4485
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] dirY = { -1, 0, 1, 0 }, dirX = { 0, -1, 0, 1 };
            int idx = 1;
            

            while (true)
            {
                int N = int.Parse(Console.ReadLine());

                if (N == 0)
                    break;

                int[,] board = new int[N, N];
                int[,] visited = new int[N, N];

                for (int i = 0; i < N; i++)
                {
                    string[] input = Console.ReadLine().Split();

                    for (int j = 0; j < N; j++)
                    {
                        board[i, j] = int.Parse(input[j]);
                        visited[i, j] = 10000;
                    }
                }

                PriorityQueue<int[], int> pq = new PriorityQueue<int[], int>();
                pq.Enqueue(new int[] { board[0, 0], 0, 0 }, board[0, 0]);
                visited[0, 0] = board[0, 0];

                while (pq.Count > 0)
                {
                    int[] now = pq.Dequeue();
                    int nowtime = now[0], nowY = now[1], nowX = now[2];

                    for (int i = 0; i < 4; i++)
                    {
                        int nextY = nowY + dirY[i], nextX = nowX + dirX[i];

                        if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= N)
                            continue;

                        if (visited[nextY, nextX] != 10000)
                            continue;

                        int nexttime = nowtime + board[nextY, nextX];
                        visited[nextY, nextX] = nexttime;
                        pq.Enqueue(new int[] { nexttime, nextY, nextX }, nexttime);
                    }
                }

                Console.WriteLine($"Problem {idx}: {visited[N - 1, N - 1]}");
                idx++;
            }
        }
    }
}