[BOJ 1261] 알고스팟 (C++)

https://www.acmicpc.net/problem/1261

1261번: 알고스팟

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

class Node{
    public:
        int y;
        int x;
        int cost;
        Node(int y, int x, int cost){
            this->y=y;
            this->x=x;
            this->cost=cost;
        }
};

struct cmp{
    bool operator()(const Node &a, const Node &b){      //최소 힙을 위한 비교자
        return a.cost>b.cost;
    }
};

int main(){
    int M, N;
    string s;
    cin>>M>>N;
    string map[N];
    priority_queue<Node, vector<Node>, cmp> pq;
    int dist[N][M];
    for (int i=0; i<N; i++){
        cin>>s;
        map[i]=s;
    }
    for (int i=0; i<N; i++){
        for (int j=0; j<M; j++){
            dist[i][j]=INF;
        }
    }
    dist[0][0]=0;
    pq.push(Node(0,0,0));
    while (!pq.empty()){
        Node now=pq.top();
        pq.pop();
        if (now.y==N-1 && now.x==M-1){
            break;
        }
        if (now.cost>dist[now.y][now.x]){
            continue;
        }
        for (int i=0; i<4; i++){
            int ny=now.y+dy[i];
            int nx=now.x+dx[i];
            if (ny<0 || nx<0 || ny>=N || nx>=M){
                continue;
            }
            int newcost=(map[ny][nx]=='0')? 0 : 1;
            if (dist[ny][nx]>now.cost+newcost){ //작을 경우에만 갱신
                dist[ny][nx]=now.cost+newcost;
                pq.push(Node(ny,nx,dist[ny][nx]));
            }
        }
    }
    cout<<dist[N-1][M-1]<<"\n";
    return 0;
}

처음에 봤을때 BFS 문젠가 싶었지만 문제에서 요구하는 조건이 '최소의 벽을 뚫는 경우' 였다. 최단 거리가 아니라.

즉 벽의 개수를 가중치로 해서 다익스트라 알고리즘을 사용하는 문제이다.

 

벽일 경우엔 cost에 1을 더하고, 빈 방일 경우엔 cost에 0을 더해 가장 최소의 가중치를 가지고 도착점에 도달할 수 있도록 한다.

 

dist[i]는 출발지에서 i까지 가는데 필요한 뚫어야될 최소의 벽의 개수이다.

dist[i]가 " 현재 지점까지 오는데 필요한 cost+현재 지점에서 다음지점까지 가는데 필요한 cost "보다 크다면 후자의 것으로 갱신하여 우선순위 큐에 넣어준다.