[C/C++] 백준 #2178 미로 탐색(너비 우선 탐색)

미로 탐색은 대표적인 그래프 탐색과 관련되어 풀 수 있는 문제입니다.  길이 여러개이고, 움직일 때 비용이 똑같다고 한다면, 다익스트라와 같이 우선순위큐를 사용하는 알고리즘을 이용하지 않고, 너비 우선 탐색을 이용해도 됩니다.

 

문제의 링크입니다.

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

이번 미로 탐색은 최단 경로를 찾아야 한다는 표현이 있지만, 고전적인 미로 탐색 문제입니다.

 

maze

 

너비우선탐색 알고리즘을 이용하였습니다.  출발점에서부터 너비우선탐색을 하다가 도착지점에 도착하면 바로 종료를 합니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2178 - Searching Maze
//        - by Aubrey Choi
//        - created at 2019-07-30
//------------------------------------------------
#include <stdio.h>
#include <queue>

int main()
{
    int n, m;
    char map[100][104];
    std::queue<int> q;
    scanf("%d%d", &n, &m);
    for(int i=0;i<n;i++) scanf("%s", map[i]);
    q.push(1<<16);
    map[0][0]='0';
    for( ; ; )
    {
        int s = q.front(); q.pop();
        int p = s>>16, r = (s&65535)/100, c = (s&65535)%100;
        if(r==n-1 && c==m-1) { printf("%d\n", p); break; }
        int d[4][2] = { 0, 1, 1, 0, 0, -1, -1, 0 };
        for(int i = 0; i < 4; i++)
        {
            int nr = r+d[i][0], nc = c+d[i][1];
            if(nr<0||nr>=n||nc<0||nc>=m||map[nr][nc]=='0') continue;
            q.push(((p+1)<<16)|(nr*100+nc));
            map[nr][nc]='0';
        }
    }
}