[BFS]백준2178번 미로탐색

백준2178번 미로 탐색

단순 BFS로 구현할 수 있는 문제였다.

BFS로 경로 탐색을 할 경우 목적지에 도착한 경우는 최단 경로가 보장된다.

편의상 각 칸이 레벨을 가지고 있다고 가정한다.

따라서 처음 출발 위치에서 레벨 1로 시작해서, 한 칸 이동할 때마다 레벨을 이전 칸의 레벨 + 1로 설정한다.

목적지에 도착했을 때는 해당 칸의 레벨을 출력한다.

단순히 몇 번 이동했는지를 출력하면 전체 1의 개수가 되기 때문에 정답이 될 수 없다.

3차원 배열, tuple 혹은 추가 배열을 이용해 각 칸의 레벨을 저장하여 구현할 수 있다.

#include <iostream>
#include <queue>
#include <string>

using namespace std;

int N, M;
int arr[101][101];
int level[101][101];
bool visited[101][101] = {false,};

int x_iter[4] = {1,0,-1,0};
int y_iter[4] = {0,1,0,-1};

int main(){
    cin >> N >> M;
    for(int i=0;i<N;i++){
        string s;
        cin >> s;
        for(int j=0;j<M;j++){
            arr[i][j] = s[j]-'0';
        }
    }
    queue<pair<int,int> > q;
    q.push(make_pair(0,0));
    visited[0][0] = true;
    level[0][0] = 1;
  
    while(!q.empty()){
        pair<int,int> cur = q.front();
        q.pop();
        if(cur.first == N-1 && cur.second == M-1){
            cout << level[cur.first][cur.second];
            break;
        }
        
        for(int i=0;i<4;i++){
            int tmp_y = cur.first + y_iter[i];
            int tmp_x = cur.second + x_iter[i];

            if(tmp_x >= 0 && tmp_x < M && tmp_y >= 0 && tmp_y <N){
                if(!visited[tmp_y][tmp_x] && arr[tmp_y][tmp_x] == 1){
                    q.push(make_pair(tmp_y,tmp_x));
                    level[tmp_y][tmp_x] = level[cur.first][cur.second] + 1;
                    visited[tmp_y][tmp_x] = true;
                }
            }
        }
    }
//    cout << count << "\n";
    
}