[백준] 2178번 미로 탐색 (C++)

문제 주소

백준 2178번 미로 탐색

알고리즘

BFS

힌트

BFS를 하자.

 

풀이

BFS의 가장 기초적인 문제이다. 문제에서 미로 탈출이 가능한 입력만 주어진다고 했다. 1이면 갈 수 있고 0이면 갈 수 없기 때문에 1이고 check가 되어 있지 않는 곳만 탐색을 해주면 된다.

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

typedef struct dot{
    int a, b;
};

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

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});
    check[1][1]=1;
    int ans=0;

    while(!q.empty()){
        ans++;
        int size=q.size();
        for(int i=0;i<size;i++){
            int a=q.front().a,b=q.front().b;
            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(!in[na][nb] || check[na][nb] || na>n || nb>m||na<1||nb<1)
                    continue;
                q.push({na,nb});
                check[na][nb]=1;
            }
        }
    }
}

백준 2178번 미로 탐색