4485번

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

이 문제는 다익스트라 알고리즘을 이용해서 풀 수 있다.

(0,0)에서 (n-1,n-1) 까지의 최단거리를 구하면 되고, 주어진 값들을 가중치라고 생각하고 풀면 되기 때문이다.

근데 내가 실수했던 점은

priority queue 를 이용해서 다익스트라를 풀 때, 처음 정점의 dist는 0 으로, 나머지 정점은 INF 로 놓고 풀게 된다.

그런데 이 문제에서는 처음에 정점의 dist 값이 0 이 아닌 값으로 주어질 수 있다.

그리고 priority queue 에서는 가장 작은 값을 구하기 위해 , dist 에 집어넣을 때 -1 을 곱해서 집어 넣는다.

즉, 처음 정점을 0 으로 했을 때, 문제가 없지만 다른 수를 넣을 경우 부호가 바뀌어 문제가 발생하게 된다.

그래서

처음 시작점을 0 으로 하고 , 마지막 답을 구하고 거기에 처음 시작점의 값을 넣어서 문제를 해결했다.

<정답 코드>

#include<iostream>
#include<queue>
#include<vector>
 
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
 
using namespace std;
const int INF = 987654321;
int main()
{
    int i = 0;
    int n;
    while (scanf("%d", &n) && n!=0)
    {
        i++;
        vector<vector<int>> map(n, vector<int>(n));
        vector<vector<int>> dist(n, vector<int>(n));
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                dist[i][j] = INF;
            }
        }
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                scanf("%d", &map[i][j]);
            }
        }
 
        priority_queue<pair<pair<int, int>,int>> pq;
        dist[0][0] = 0;
        pq.push({ { 0,0 },dist[0][0] });
 
        while (!pq.empty())
        {
            int x = pq.top().first.first;
            int y = pq.top().first.second;
            int cost = -pq.top().second;
            pq.pop();
 
            if (cost > dist[x][y]) { continue; };
 
            for (int d = 0; d < 4; d++)
            {
                int nx = x + dx[d];
                int ny = y + dy[d];
                
                if (nx >= 0 && ny >= 0 && nx < n && ny < n)
                {
                    int w = map[nx][ny];
 
                    if (dist[nx][ny] > cost + w)
                    {
                        dist[nx][ny] = cost + w;
                        pq.push({ {nx,ny},-dist[nx][ny] });
                    }
                }
            }
            
        }
 
        printf("Problem %d: %d\n", i,dist[n - 1][n - 1]+map[0][0]);
 
    }
 
    return 0;
}