[C++] 벽 부수고 이동하기

백준 2206번

solved ac 클래스 3이 끝나서 클래스 4 문제들을 풀기 시작했다

한참 많이 풀었던 bfs 유형이라 금방 풀 수 있었다

 

먼저 문제에서 요구하는 최단경로라는 키워드를 통해 bfs를 쓰면 되겠다고 판단했다

그 다음 벽을 단 한번만 부술 수 있으니 벽을 이미 부순 상태인지, 앞으로 부술 수 있는지만 나누어주었다

visit 배열 또한 벽을 부순 상태로 방문한 것인지, 부수지 않고 방문했는지 따로 저장했다

 

반복문 안에서의 조건은 아래와 같이 세가지로 나누었다

1. 벽도 없고 방문한 적도 없으며 앞으로 벽을 부술 수 있다

2. 벽이 없고 이미 벽을 부수었고 벽을 부순 상태로는 처음 방문한다

3. 벽이 있고 아직 벽을 부수지 않았다

이때 벽을 부순 칸을 다시 방문하는 것은 최단 경로가 아닌것이 자명하므로 벽을 부술때 실제 벽의 위치가 저장된 배열의 값들을 바꾸어주지는 않았다

 

이렇게 세가지 조건을 사용하는 점이 기존에 많이 풀었던 2차원 bfs와는 다른 점이었던 문제!

 

#include <stdio.h>
#include <queue>
 
using namespace std;
 
int graph[1005][1005];
int visit[1005][1005][2]; // not crash, crash
 
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
 
class Status{
    public:
        int crashed; // 1 if crashed
        int count;
        int x;
        int y;
};
 
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",&graph[i][j]);
        }
    }
 
    visit[0][0][0] = 1;
    visit[0][0][1] = 1;
    
    queue<Status> q;
    Status stat = {0,1,0,0};
    q.push(stat);
    while(!q.empty()){
        int crashed = q.front().crashed;
        int count = q.front().count;
        int x = q.front().x;
        int y = q.front().y;
        //printf("%d %d %d %d\n",crashed,count,x,y);
 
        q.pop();
        if(x==N-1 && y==M-1){
            printf("%d\n",count);
            return 0;
        }
 
        for(int i = 0 ; i < 4 ; i++){
            int next_x = x + dx[i];
            int next_y = y + dy[i];
            if(next_x<0 || next_x >= N || next_y < 0 || next_y >= M) continue;
            if(graph[next_x][next_y]==0 && crashed==0 && visit[next_x][next_y][0]== 0 ){
                visit[next_x][next_y][0] = 1;
                Status stat = {crashed, count+1, next_x, next_y};
                q.push(stat);  
            }
            if(graph[next_x][next_y]==0 && crashed==1 && visit[next_x][next_y][1]== 0 ){
                visit[next_x][next_y][1] = 1;
                Status stat = {crashed, count+1, next_x, next_y};
                q.push(stat);
            }
            if(graph[next_x][next_y]==1 && crashed==0 && visit[next_x][next_y][1] == 0){
                visit[next_x][next_y][1] = 1;
                Status stat = {1,count+1, next_x, next_y};
                q.push(stat);
            }
        }
 
    }
    printf("-1\n");
}