BOJ : 2206 벽 부수고 이동하기

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

github : https://github.com/JEONG-SEUNGWOOK/BOJ/blob/master/2206.cpp

BFS를 이용한 미로찾기에서 벽을 부수는 스킬이 추가되었다.

종종 벽을 부순다거나 폭탄이 주어진다거나 하는 문제 유형이 있는데 그 중의 기본 문제이다.

내 해결 방법은 방문체크(isVisited)배열을 한 차원 더 늘려 벽을 부쉈을 때, 안 부쉈을 때를 나눠 탐색했다.

더 좋은 해결 방법이 있으면 댓글 남겨주시면 감사하겠습니다.

#include <iostream>
#include <queue>
using namespace std;

struct Pos{
    int x,y,bomb;
};
int N,M,dis=1,ans=0;
char map[1001][1001];
bool isVisited[1001][1001][2];
int px[4]={1,-1,0,0};
int py[4]={0,0,1,-1};

queue<Pos> q;

int main(){
    cin>>N>>M;
    
    for(int i=0; i<N; i++)
        cin>>map[i];
    
    Pos s;
    s.x = 0, s.y = 0, s.bomb = 0;
    q.push(s);
    isVisited[s.x][s.y][s.bomb]=true;
    
    while(!q.empty()){
        int q_size = q.size();
        while(q_size--){
            Pos p = q.front(); q.pop();
            int x= p.x, y=p.y, b=p.bomb;
            
            //cout<<x<<" "<<y<<" "<<b<<endl;
            if(x==N-1 && y==M-1){
                ans=dis;
                cout<<ans<<'\n';
                return 0;
            }
            for(int i=0; i<4;i++){
                if(x+px[i]>=0 && x+px[i]<N && y+py[i]>=0 && y+py[i]<M && !isVisited[x+px[i]][y+py[i]][b] && map[x+px[i]][y+py[i]]=='0'){
                    
                    isVisited[x+px[i]][y+py[i]][b] = true;
                    Pos t;
                    t.x=x+px[i], t.y=y+py[i], t.bomb=b;
                    q.push(t);
                }
            }
            if(b==0){
                for(int i=0; i<4;i++){
                    if(x+px[i]>=0 && x+px[i]<N && y+py[i]>=0 && y+py[i]<M && !isVisited[x+px[i]][y+py[i]][b]){
                        
                        isVisited[x+px[i]][y+py[i]][b+1] = true;
                        Pos t;
                        t.x=x+px[i], t.y=y+py[i], t.bomb=b+1;
                        q.push(t);
                        
                    }
                }               
            }
        }
        dis++;
    }
    if(ans==0)cout<<-1<<'\n';
}