[BOJ] 2206. 벽 부수고 이동하기

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

2206번: 벽 부수고 이동하기

시작 칸에서 마지막 칸까지의 최단 거리를 구하는 문제이기 때문에 bfs로 풀 수 있다.

다른 분의 풀이를 보니 dfs로 엄청 효율적으로 푸셨는데 코드 참고해서 나도 다시 풀어봐야겠다...

 

 

먼저 이 문제에서 중요한 포인트는 벽을 한 개 부수고 이동할 수 있다는 점이다. 이 부분이 이 문제의 어려운 점이다

즉, (x, y)칸에 도착했을 때 그 칸에 그냥 왔는지와 벽을 부수고 왔는지 구분해 주어야한다.

그래서 3차원 배열로 구현했다. 벽을 부수지 않은 경우[x][y][0], 부 순경 우 [x][y][1] 에 이동 경로를 저장했다.

이동할 칸이 벽인 경우, 아직 벽을 부수지 않았고 해당 칸에 아직 방문하지 않았으면 벽을 부수고 이동할 수 있다.

길인 경우에는 그냥 방문하지 않았으면 바로 큐에 넣어준다.

 

 

개인적으로 은근히 헷갈렸던 부분은 이동 경로의 최솟값을 찾아주는 부분이었다.

우선 (n-1, m-1) 칸에 저장되어 있기는 하지만, 벽을 부수고 온 경우가 더 적은 지 벽을 부수지 않고 바로 온경우가 더 적은지

알 수 없으므로 비교해주어야 한다. 그리고 두 곳에 모두 값이 0이라면 -1을 출력해주어야 한다.

나는 먼저 바로 온 경우(d[n-1][m-1][0])을 최솟값(min)으로 해놓고 벽을 부수고 온 경우(d[n-1][m-1][1])가 0이 아닌 경우에 값을 다시 비교해주었다.

 

 

결과적으로 둘 다 0 값을 가지고 있으면 min값도 0이 되므로 도착하지 못한 경우가 되고 -1을 출력한다.

그렇지 않은 경우에는 최솟값을 가지고 있는 min을 출력해준다.

 

#include <cstdio>
#include <queue>
using namespace std;
 
int map[1000][1000];
int d[1000][1000][2];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
 
int main() {
 
   
    int n, m;
    scanf("%d %d", &n, &m);
 
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
 
 
    //시작 칸을 큐에 넣어준다.
    queue<pair<pair<int, int>, int> > q;
    q.push(make_pair(make_pair(0,0),0));
 
    //시작칸도 포함이므로 1부터 시작
    d[0][0][0] = 1;
 
 
    while(!q.empty()) {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int z = q.front().second;
        q.pop();
 
        for(int i=0; i<4; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];
 
            //범위 체크
            if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            
            //벽인 경우
            //z == 0 이고 (벽을 부수지 않았고), 벽을 부순상태인 다음 칸에 아직 방문하지 않은 경우
            if(map[nx][ny] == 1 && z == 0 && d[nx][ny][1] == 0) {
                q.push(make_pair(make_pair(nx,ny),1));
                d[nx][ny][1] = d[x][y][z] + 1;
            } else if(map[nx][ny] == 0 && d[nx][ny][z] == 0) {
 
                //길인 경우 이동할 칸에 방문하지 않았으면 방문
                q.push(make_pair(make_pair(nx,ny),z));
                d[nx][ny][z] = d[x][y][z] + 1;
            }
            
        }
        
    }
 
 
    //마지막칸의 최솟값을 찾아준다.
    int min =  d[n-1][m-1][0];
    if(min != 0) {
        if(d[n-1][m-1][1] != 0 && min > d[n-1][m-1][1]) {
            min = d[n-1][m-1][1];
        }
    } else {
        if(d[n-1][m-1][1] != 0) {
            min = d[n-1][m-1][1];
        }
    }
 
 
    //도착하지 못한 경우 -1을 출력
    if(min == 0){
        printf("%d", -1);
    } else {
        printf("%d",min);
    }     
 
    return 0;
}