2178 미로 탐색

문제 링크

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

풀이

(1, 1)에서 시작하여 bfs를 통해 인접한 좌표들을 돌며 거리를 업데이트한다. 갈 수 있는 칸인 경우 그 이전까지의 거리+1을 해주면서 (N,M)까지 가면 된다. bfs가 종료되면 (N,M)칸의 값을 출력한다.

C++ 코드

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

using namespace std;

int N, M;
int arr[101][101];
bool visit[101][101];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

void bfs(pair<int, int> V){
    queue<pair<int, int>> q;
    q.push(make_pair(V.first, V.second));
    visit[V.first][V.second] = true;
    
    while(!q.empty()){
        V = q.front();
        q.pop();
        for(int i=0; i<4; i++){
            int nx = V.first+dx[i];
            int ny = V.second+dy[i];
            if(!visit[nx][ny] && 0<nx && nx<=N && 0<ny && ny<=M && arr[nx][ny] == 1){
                q.push(make_pair(nx, ny));
                visit[nx][ny] = true;
                arr[nx][ny] = arr[V.first][V.second] + 1;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin>>N>>M;
    
    for(int i=0; i<N; i++){
        string str;
        cin>>str;
        for(int j=0; j<M; j++){
            arr[i+1][j+1] = str[j] - '0';
        }
    }
    
    bfs(make_pair(1,1));
    
    cout<<arr[N][M]<<endl;
    
    return 0;
}