[백준] 2206번 벽 부수고 이동하기 (C++)

문제 주소

백준 2206번 벽 부수고 이동하기

알고리즘

BFS

힌트

어떤 위치에 온 상태가 벽을 부수고 온 것인지, 벽을 부수지 않고 온 것인지 구분 해야 한다.

 

 

풀이

위치(a, b)와 상태(w : 벽을 부쉈다면 1 부수지 않았다면 0)를 원소로 가지는 dot구조체를 만들어 준다. check배열도 위치와 상태를 담을 수 있도록 3차원으로 선언 해 준다. 현재의 위치가 목표 위치라면 ans를 출력하고 main 함수를 종료 해 준다.q를 다 확인 할 때까지 목표점에 도착하지 못하였다면 목표점에 도달할 수 없는 것이므로 -1을 출력해준다. 벽이 있고 벽을 뚫지 않았다면 q에 넣어주고 벽이 없다면 check배열을 하여 중복되지 않도록 q에 넣어준다.

#include<stdio.h>
#include<queue>
using namespace std;

typedef struct dot{
    int a,b,w;
};

queue<dot> q;
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int in[1001][1001];
int check[1001][1001][2];

int main(){
    int n,m;
    scanf("%d %d",&n,&m); 
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%1d",&in[i][j]);

    q.push({1,1,0});
    check[1][1][0]=1;

    int ans=1;
    while(!q.empty()){
        int size=q.size();
        for(int i=0;i<size;i++){
            int a=q.front().a,b=q.front().b,w=q.front().w; 
            q.pop();


            if(a==n&&b==m){
                printf("%d",ans);
                return 0;
            }

            for(int i=0;i<4;i++){
                    int na=a+dir[i][0],nb=b+dir[i][1];

                    if(na>n || nb>m || na<1 || nb<1)
                        continue;

                    if(in[na][nb] && !w){
                        q.push({na,nb,w+1});
                        check[na][nb][w+1]=1;
                    }
                    else if(!in[na][nb] && !check[na][nb][w]){
                        q.push({na,nb,w});
                        check[na][nb][w]=1;
                    }
            }


        }

        ans++;

    }    
    printf("-1");
}

백준 2206번 벽 부수고 이동하기