[백준] 1261번 알고스팟

[적용한 알고리즘]

다익스트라

 

[아이디어]

https://akim9905.tistory.com/45 와 똑같다. 벽이 cost가 되는거다.

 

[생각의 흐름 / 절차] 

내용

 

[교훈]

n, m으로 장난쳐놨다. 찾는데 한참 걸림. 조심들 하세요.

 

<코드>

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int MAX = 101;
const int INF = 1000000000;

int dirx[] = {-1, 1, 0, 0};
int diry[] = {0, 0 ,1, -1};
int n, m;
struct Ver{
    int x, y, dist;
    bool operator < (const Ver &v) const{
        return dist > v.dist;
    }
};

bool inMap(int x, int y){
    if (1 <= x && x <= n && 1 <= y && y <= m) return true;
    return false;
}

int main(){
    bool visited[MAX][MAX] = { 0 };
    int map[MAX][MAX] = { 0 };
    int dist[MAX][MAX] = { 0 };

    scanf("%d %d", &m, &n);
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            scanf("%1d", &map[i][j]);
            dist[i][j] = INF;
        }
    }

    dist[1][1] = 0;
    priority_queue<Ver> PQ;
    PQ.push({1, 1, dist[1][1]});

    while (!PQ.empty()) {
        Ver cur;
        do {
            cur = PQ.top();
            PQ.pop();
        } while (!PQ.empty() && visited[cur.x][cur.y]);

        if (visited[cur.x][cur.y]) break;
        visited[cur.x][cur.y] = true;

        for (int k = 0; k < 4; k++) {
            int nx = cur.x + dirx[k];
            int ny = cur.y + diry[k];

            if (inMap(nx, ny)) {
                if (dist[nx][ny] > dist[cur.x][cur.y] + map[nx][ny]) {
                    dist[nx][ny] = dist[cur.x][cur.y] + map[nx][ny];
                    PQ.push({nx, ny, dist[nx][ny]});
                }
            }
        }
    }

    printf("%d", dist[n][m]);
    return 0;
}