(C++) - 백준(BOJ) 1261번 : 알고스팟

www.acmicpc.net/problem/1261

1261번: 알고스팟

다익스트라로 푼 문제였습니다.

 

풀이방법

 1. nx행,ny열에 도착했을 때 부수는 최소 벽의 개수를 저장할 dist배열을 선언해 큰 값 0x3f3f3f3f로 초기화해줍니다. priority_queue를 이용해 항상 왼쪽 위 정점을 우선으로 볼 수 있도록 합니다.

 

 2. nx행 ny열이 벽인 경우에는 벽을 부숴야하는지를 확인해줍니다. 현재지점(x,y)에서 nx,ny로 도착하기 위해서는 벽을 부숴야하므로 dist[x][y] + 1의 값과 dist[nx][ny]값을 비교해서 전자의 값이 더 작다면 갱신해주고 pq에 push해줍니다.

아닌경우에는 벽을 부술 필요가 없으므로 dist[nx][ny]와 dist[x][y]를 비교해 nx,ny가 더 작다면 pq에 push해줍니다.

  

 3. 0,0 인덱스에서 시작했으므로 dist[r-1][c-1]를 출력합니다.

 

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
using pii = pair<int,int>;
int r,c;
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};

int board[101][101];
int dist[101][101];

queue<pii> pq;

int dijkstra() {
	pq.push({ 0,0 });
    dist[0][0] = 0;
    while(!pq.empty()){
        int x = pq.front().first;
        int y = pq.front().second;
        pq.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0 > nx || nx >= r || 0 > ny || ny >= c) continue;
            if(board[nx][ny]){
                if(dist[nx][ny] > dist[x][y] + 1){
                    dist[nx][ny] = dist[x][y] + 1;
                    pq.push({nx,ny});
                }
            }else{
                if(dist[nx][ny] > dist[x][y]){
                    dist[nx][ny] = dist[x][y];
                    pq.push({nx,ny});
                }
            }
        }
    }    
    return dist[r-1][c-1];
}

int main(){
    cin >> c >> r;
    for(int i = 0; i < r; i++)
        for(int j = 0; j < c; j++)
            scanf("%1d",&board[i][j]);

    for(int i = 0; i < r; i++)
        for(int j = 0; j < c; j++)
            dist[i][j] = INF;

    cout << dijkstra();
}