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

문제

접근 방법

여러 길이 존재한다면 도둑 루피를 최소로 가져가는 길부터 확인하는 것이 좋은 방법일 것이다.
최소인 지점부터 확인하는 방식으로 탐색하는 것은 다익스트라이다.
다익스트라를 활용하여서 해결하면 된다.

코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, pair<int, int>> pii;
int N, map[125][125], dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
bool visted[125][125];
bool input()
{
    cin >> N;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
        {
            cin >> map[i][j];
            visted[i][j] = false;
        }
    return N;
}
int solve()
{
    visted[0][0] = true;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({map[0][0], {0, 0}});
    while (!pq.empty())
    {
        pii cur = pq.top();
        pq.pop();
        int val = cur.first, y = cur.second.first, x = cur.second.second;
        if (y == N - 1 && x == N - 1)
            return val;
        for (int i = 0; i < 4; ++i)
        {
            int ny = y + dy[i], nx = x + dx[i];
            if (ny < 0 || nx < 0 || ny >= N || nx >= N || visted[ny][nx])
                continue;
            visted[ny][nx] = true;
            pq.push({val + map[ny][nx], {ny, nx}});
        }
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int tc = 1;
    while (input())
        cout << "Problem " << tc++ << ": " << solve() << "\n";
    return 0;
}

풀이

다익스트라를 알고 있다면 쉽게 풀 수 있는 문제이다.
우선순위 큐에 존재하는 값이 N-1, N-1 위치에 있다면 최소 비용으로 도달했다는 뜻이므로 더 확인해 볼 필요는 없다.

닌텐도 문제집에 집어넣으면서 언젠간 풀어야지 했던 문제였다.