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

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

 

다익스트라 문제였다. 그런데 이제 어떤 정점에서 다른정점까지의 비용이 1 4 8 이런식으로 주어지는 게 아니라,

2차원 배열로 어떤 정점에 도착했을 때의 비용이 주어지는.

그러니깐, 한곳에서 다른곳으로 이동가능한 간선이 주어지는 게 아니라 bfs나 dfs문제 풀때처럼 상하좌우로 움직이는 거 가능하고, 어디 도착하면 거기 비용이 플러스 되는 형식이다. 

재밌었다.

#include <bits/stdc++.h>
using namespace std;
int n;
int a[130][130];
int num;
int inf = 1e9;
int d[130][130];
int dirY[4] = {1, -1, 0, 0};
int dirX[4] = {0, 0, 1, -1};
int main()
{
    int p = 1;
    while (1)
    {
        cin >> n;
        if (n == 0)
        {
            break;
        }
        memset(a, 0, sizeof(a));
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> num;
                a[i][j] = num;
            }
        }

        fill(&d[0][0], &d[0][0] + 130 * 130, inf);
        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq; // {비용, 정점}

        d[0][0] = a[0][0];
        pq.push({d[0][0], {0, 0}});
        while (pq.size())
        {
            auto cur = pq.top();
            pq.pop();
            int price = cur.first;
            int curY = cur.second.first;
            int curX = cur.second.second;

            if (d[curY][curX] < price)
            {
                continue;
            }

            for (int i = 0; i < 4; i++)
            {
                int nextY = curY + dirY[i];
                int nextX = curX + dirX[i];
                if (nextY < 0 || nextY >= n || nextX < 0 || nextX >= n)
                {
                    continue;
                }

                int nextPrice = a[nextY][nextX];
                if (d[nextY][nextX] <= price + nextPrice)
                {
                    continue;
                }
                d[nextY][nextX] = price + nextPrice;
                pq.push({d[nextY][nextX], {nextY, nextX}});
            }
        }
        cout << "Problem " << p << ": " << d[n - 1][n - 1] << "\n";
        p++;
    }
    return 0;
}