백준 2178 미로 탐색 - C++

 

BFS를 이용한 최단거리 구하기 문제이다.

(1,1)에서 시작하여 (N,M)으로 가는 최단거리를 구해야 한다.

현재 위치(i,j)에서 다음 위치(상하좌우)로 갈 수 있을 때 다음 위치의 값을 현재 위치의 값 +1로 하게 되면 최종적으로 (N,M)으로 가는 최소 비용을 구하게 된다.

 

#include <cstdio>
#include <queue>
using namespace std;
int A[101][101];
bool check[101][101];
int low[] = {-1, +1, 0, 0};
int col[] = {0, 0, -1, +1};
int N,M;
void bfs(int i, int j){
    check[i][j] = true;
    queue<pair<int,int>> q;
    q.push(make_pair(i,j));
    while(!q.empty()){
        int curI = q.front().first;
        int curJ = q.front().second;
        q.pop();
        //상하좌우 총 4번 비교
        for(int i=0; i<4; i++){
            int valI = curI+low[i];
            int valJ = curJ+col[i];
            if( ( valI >= 0 && valI <= N ) && ( valJ >= 0 && valJ <= M ) ){
                if(A[valI][valJ] != 0 && check[valI][valJ] != true){
                    A[valI][valJ] = A[curI][curJ]+1;
                    q.push(make_pair(valI,valJ));
                    check[valI][valJ] = true;
                }
            }
            
        }
    }
    
}
int main()
{
    scanf("%d %d", &N, &M);
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            scanf("%1d", &A[i][j]);
        }
    }
    bfs(1,1);
    printf("%d",A[N][M]);
    return 0;
}