백준 2178번 C++ 풀이

#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;
int N, M;
int buffer[1000][1000];
deque<pair<int, int>> dq;
struct Dir {
    int y, x;
};
Dir moveDir[4] = {{1,0}, {-1, 0},{0, 1}, {0,-1}};

void BFS(){
    int w = 0;
    if (dq.empty()){
        return;
    }
    while (!dq.empty()){
        int currentSize = dq.size();
        w++;
        for (int i =0; i< currentSize; i++){

            int x = dq.front().first;
            int y = dq.front().second;
            for (int j = 0; j< 4 ; j++){
                int nextY = y+ moveDir[j].y;
                int nextX = x+ moveDir[j].x;
                if (0 <= nextY && nextY < N &&
                    0 <= nextX && nextX < M &&
                    buffer[nextX][nextY] == 1
                    ){
                    if (nextX == M-1 && nextY == N-1 ){
                        cout << w +1 << endl;
                        return;
                    }
                    buffer[nextX][nextY] = 0;
                    dq.push_back(make_pair(nextX, nextY));
                }
            }
            dq.pop_front();

        }

    }
}

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

    cin >> N >> M;
    for (int y = 0; y< N; y++){
        for (int x = 0; x<M; x++){
            char temp;
            cin >> temp;
            if (temp == '0' ) {
                buffer[x][y] = 0;
            }else {
                buffer[x][y] = 1;
            }
        }
    }
    dq.push_front(make_pair(0,0));
    BFS();

    return 0;
}