[BaekJoon/백준] 2206번 벽 부수고 이동하기

 

 

14923번 미로탈출 문제와 똑같은 문제다.

 

BFS 한번으로 이 문제를 해결할 수 있다.

 

 

벽을 부순 상태에서의 이동 & 벽을 아직 부수지 않은 상태에서의 이동 두 가지를 갖고 계산해나가면 된다.

 

 

1. 벽을 아직 부수지 않은 상태에서의 이동
   VISIT[x][y][0]을 이용한다.
   벽을 만나면, 벽을 부수고 이동하고 (VISIT[next_x][next_y][1] = VISIT[x][y][0] + 1)
   벽을 만나지 않으면, 그냥 이동한다 (VISIT[next_x][next_y][0] = VISIT[x][y][0] + 1)
   
   
2. 벽을 한번 부순 상태에서의 이동
   VISIT[x][y][1]을 이용한다.
   벽을 만나지 않으면, 그냥 이동한다 (VISIT[next_x][next_y][1] = VISIT[x][y][1] + 1)
   벽을 만나면 이동할 수 없다.
   
   

벽을 부순 상태에서, 또 벽을 만나면 어차피 해당 위치는 현재 상태에서 고려해주지 못하고
벽을 부수지 않은 상태에서 해당 벽을 만났을 때 처리가 될 것이다.

 

더 자세한 내용은 위 14923번 문제 링크에 담았다.

#include <iostream>
#include <queue>
#define MAX(a,b) ((a>=b)?a:b)

using namespace std;


int N, M;

char MAP[1000][1000];
int VISIT[1000][1000][2]; // VISIT[1000][1000][0] => 벽을 부수지 않은 상태에서의 이동, VISIT[1000][1000][1] => 벽을 한번 부순 상태에서의 이동

int mx[4] = {1, -1, 0, 0};
int my[4] = {0, 0, 1, -1};

int bfs() {
    
    queue<pair<int, pair<int, int>>> que;
    
    que.push({0, {0, 0}});
    VISIT[0][0][0] = 1;
    
    int type, x, y, tx, ty;
    
    while(!que.empty()) {
        
        type = que.front().first;
        
        x = que.front().second.first;
        y = que.front().second.second;
        
        que.pop();
        
        // 여기에 넣는 이유 => 1 1 0 같은 입력이 주어지면, 시작 그 지점이 바로 종료 지점임.
        if(x == N - 1 && y == M - 1)
            return MAX(VISIT[x][y][0], VISIT[x][y][1]); // MAX인 이유 -> 어차피 bfs이므로 최단임. VISIT[0]이 0이아닌 수로 먼저 채워지거나, VISIT[1]이 0이아닌수로 먼저 채워지거나 둘중 하나이므로, 둘 중 0이 아닌 수를 내보내기 위함.

        
        for(int i = 0; i < 4; i++) {
            
            tx = x + mx[i];
            ty = y + my[i];
            
            
            if(tx < 0 || tx >= N || ty < 0 || ty >= M)
                continue;
            
            
            
            if(type == 0) {
                // 벽을 아직 부수지 않은 이동에서
                
                if(MAP[tx][ty] == '1' && VISIT[tx][ty][1] == 0) {
                    
                    VISIT[tx][ty][1] = VISIT[x][y][0] + 1;
                    que.push({1, {tx, ty}});
                } else if(MAP[tx][ty] == '0' && VISIT[tx][ty][0] == 0) {
                    
                    VISIT[tx][ty][0] = VISIT[x][y][0] + 1;
                    que.push({0, {tx, ty}});
                }
                
                
            } else {
                // 벽을 한번 부순 상태의 이동에서
                
                if(MAP[tx][ty] == '0' && VISIT[tx][ty][1] == 0) { // 벽이 아닌 곳만 가능.
                    
                    VISIT[tx][ty][1] = VISIT[x][y][1] + 1;
                    que.push({1, {tx, ty}});
                    
                }
                
            }
            
        }
    }
    
    return -1;
    
    
}

int main() {
    
    cin >> N >> M;
    
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> MAP[i][j];
        }
    }
    
    cout << bfs() << "\n";
    
    

}

 

 

 

소요 시간 : 45분