백준 02178 - 미로 탐색

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

2178번: 미로 탐색

 

고려사항

• BFS 를 활용 - BFS를 활용하면 레벨 (몇 번 움직였는지)가 작은 순서대로 탐색하기 때문에
  먼저 (N, M) 에 도달하면 더이상 탐색 없이 return 해줄 수 있다.
• DFS를 사용하면 현재 움직인 cnt 값을 인자로 넘겨주며 값을 구할 수 있지만
  N, M 에 도달해도 다른 가지까지 탐색을 진행해야 최소값인지를 알 수 있다.
  ( 가지치기를 이용하면, 연산을 줄일 수 있긴 하지만.. )

 

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

bool map[101][101];
bool visit[101][101];
int n, m;
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, 1, -1};
queue<pair<pair<int, int>, int>> q;

int bfs(){
    int curY, curX, curCnt, nextY, nextX;

    while(!q.empty()){
        curY = q.front().first.first;
        curX = q.front().first.second;
        curCnt = q.front().second;
        q.pop();

        for(int i=0;i<4;++i){
            nextY = curY + dy[i];
            nextX = curX + dx[i];

            if(nextY == n && nextX == m){
                return curCnt + 1;
            }

            if(0 < nextY && nextY <= n && 0 < nextX && nextX <= m
                && map[nextY][nextX] && !visit[nextY][nextX]){
                q.push({{nextY, nextX}, curCnt+1});
                visit[nextY][nextX] = true;
            }
        }
    }
}

int main() {
    cin>>n>>m;
    string tmp;

    for(int i=1;i<=n;++i){
        cin>>tmp;
        for(int j=1;j<=m;++j){
            if(tmp[j-1] == '1'){
                map[i][j] = true;
            }
        }
    }

    q.push({{1,1},1});
    visit[1][1] = true;

    cout<<bfs();
    return 0;
}