BOJ2665_미로만들기

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
#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;
        return true;
    }
};

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

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

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

        int r = cur.pos[0];
        int c = cur.pos[1];

        if (cur.cost > d[cur.pos[0]][cur.pos[1]]) continue;

        for(int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + 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(false); 
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    memset(map, 0, sizeof(map));
    string temp;

    for (int i = 0; i < N; i++) {
        cin >> temp;
        for (int j = 0; j < N; j++) {
            if(temp[j] - 48 == 1) map[i][j] = 0;
            else map[i][j] = 1;
        }
    }


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

    dijkstra();

    cout << d[N-1][N-1] << endl;
}