[PS] 백준 2178번 - 미로 탐색

최단 경로 문제이므로 BFS를 사용하는 것이 적합하다.

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

using namespace std;

int m, n, a[100][100], d[100][100];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

void BFS(){
    queue<pair<int, int>> q;
    q.push({0, 0});
    d[0][0] = 1;

    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && nx < m && ny >= 0 && ny < n) {
                if(a[nx][ny] == 1 && d[nx][ny] == 0) {
                    d[nx][ny] = d[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }

    if(d[m-1][n-1] != 0) cout << d[m-1][n-1];
    else cout << -1;
}

int main(void) {
    cin >> m >> n;
    for(int i=0; i<m; i++){
        string s;
        cin >> s;
        for(int j=0; j<n; j++) a[i][j]=s[j]-'0';
    }
    BFS();
    return 0;
}