BOJ4485_녹색 옷 입은 애가 젤다지? (C++)

BFS + 다익스트라

cmp 부호 주의

#include <iostream>
#include <vector>
#include <queue>
#define INF int(1e9)

using namespace std;

struct Edge{
    int pos[2];
    int cost;
};

struct cmp {
    bool operator() (Edge a, Edge b) {
        if (a.cost <= b.cost) return false;
        else return true;
    }
};

int map[125][125];
int d[125][125];
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};
int N;



void dijkstra() {
    priority_queue <Edge, vector<Edge>, cmp> pq;
    pq.push({{0, 0}, map[0][0]});
    d[0][0] = map[0][0];

    while(!pq.empty()) {
        Edge cur = pq.top();
        pq.pop();

        if(cur.cost > d[cur.pos[0]][cur.pos[1]]) continue;
        for(int i = 0; i < 4; i++) {
            int nr = cur.pos[0] + dr[i];
            int nc = cur.pos[1] + dc[i];
            if (nr < 0 || nc < 0 || nr >= N || nc >= N) continue;
            if (d[nr][nc] <= cur.cost + map[nr][nc]) continue;
            d[nr][nc] = cur.cost + map[nr][nc];
            pq.push({{nr, nc}, d[nr][nc]});
        }
    }
}

int main (void) {
    ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

    int t = 1;
    cin >> N;

    while (N != 0) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> map[i][j];
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                d[i][j] = INF;
            }
        }

        dijkstra();

        cout << "Problem " << t << ": " << d[N-1][N-1] << endl;
        t++;

        cin >> N;
    }
}