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

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

2178번: 미로 탐색

 

BFS 문제!! 이제 경로 탐색은 어느정도 숙달된 것 같다. 이 문제는 딱히 예외 상황이 없어서 한 번에 해결할 수 있었다. visit 배열이 방문 배열이면서 해당 위치까지 도달하기 위한 최소의 칸 수가 된다. 큐에 push 할 때 visit 배열 초기화를 아래와 같이 해주면 된다.

 

visit[new_row][new_col] = visit[row][col] + 1

 

 

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

int map[100][100];
int visit[100][100];
int N, M;

void bfs(){
    int move[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
    queue<pair<int, int>> q;
    q.push({0,0});
    visit[0][0] = 1;
    
    int row, col, n_row, n_col;
    
    while(!q.empty()){
        row = q.front().first;
        col = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++){
            n_row = row + move[i][0];
            n_col = col + move[i][1];
            
            if(n_row >= 0 && n_col >= 0 && n_row < 100 && n_col < 100){
                if(map[n_row][n_col] == 1 && !visit[n_row][n_col]){
                    visit[n_row][n_col] = visit[row][col] + 1;
                    q.push({n_row, n_col});
                }
            }
        }
    }
}

int main(){
    cin >> N >> M;
    char c;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> c;
            map[i][j] = c - '0';
        }
    }
    
    bfs();
    
    cout << visit[N - 1][M - 1] << endl;
    
    return 0;
}