[알고리즘] 백준 2178

백준 2178번

전형적인 depth를 구하는 BFS 문제였다.

풀이

#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
typedef long long ll;

string s;
int N,M,x,y;
int a[104][104];
int visited[104][104];
queue<pair<int, int>> q;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;
    for(int i=0; i<N; i++){
        cin >> s;
        for(int j=0; j<M; j++){
            a[i][j] = s[j] - '0';
        }
    }
    int dy[4] = {-1, 0, 1, 0};
    int dx[4] = { 0, 1, 0,-1};
    visited[0][0] = 1;
    q.push({0, 0});
    while(q.size()){
        tie(y,x) = q.front(); q.pop();
        for(int i=0; i<4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny < 0 || nx < 0 || ny >= N || nx >= M ) continue;
            if(a[ny][nx] == 0 || visited[ny][nx]) continue;
            visited[ny][nx] = visited[y][x] + 1;
            q.push({ny, nx});
        }
    }
    cout << visited[N-1][M-1];
    
    return 0;
}