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

문제

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

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

풀이

처음에 오른쪽, 아래쪽으로만 이동 가능한 줄 알고, 'DP로 쉽게 풀리겠네'라고 잘못 생각했다.

상하좌우 이동이 모두 가능하기 때문에 다익스트라로 해결해야 한다.

struct 타입을 새로 정의하고 우선순위 큐에 넣으면 비교가 불가하기 때문에 에러가 발생한다.

오퍼레이터를 정의해줘서, 오름차순으로 PQ에 들어가게 해 주었다.

소스 코드

#include <iostream>
#include <queue>
#define INF 987654321
using namespace std;
 
int N;
int Rupee[125][125];
int Sum[125][125];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
 
struct node
{
    int rupee;
    int x;
    int y;
    // 오름차순 정렬
    bool operator<(const node& i) const {
        return rupee > i.rupee;
    }
};
 
void Dijkstra()
{
    priority_queue<node> PQ;
    PQ.push({ Rupee[0][0], 0, 0 });
    Sum[0][0] = Rupee[0][0];
    while (!PQ.empty())
    {
        int rupee = PQ.top().rupee;
        int x = PQ.top().x;
        int y = PQ.top().y;
        PQ.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int nRupee = Rupee[ny][nx];
            if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
                if (Sum[ny][nx] > rupee + nRupee) {
                    Sum[ny][nx] = rupee + nRupee;
                    PQ.push({ Sum[ny][nx], nx, ny });
                }
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int cnt = 0;
    while (1) {
        cnt++;
        cin >> N;
        if (N == 0) {
            break;
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> Rupee[i][j];
                Sum[i][j] = INF;
            }
        }
        Dijkstra();
        cout << "Problem " << cnt << ": " << Sum[N - 1][N - 1] << '\n';
    }
    return 0;
}