(C++) - 백준(BOJ) 2178번 : 미로 찾기 답

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

간단한 BFS문제였습니다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int h, w, N, M,cnt, d[101][101], a[101][101],c[101][101], dh[] = { 0,0,-1,1 }, dw[] = { -1,1,0,0};
void BFS(int h, int w)
{
    queue <pair<int, int> > q;
    q.push(make_pair(h, w));
    //체크
    d[h][w] = ++cnt;
    c[h][w] = 1;
    while (!q.empty())
    {
        h = q.front().first;
        w = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int nh = h + dh[i];
            int nw = w + dw[i];
            
            if (0 <= nh && nh < N && 0 <= nw && nw < M)
                if (a[nh][nw] == 1 && c[nh][nw] == 0)//원점으로부터의 거리가 같은 점끼리는 같은 거리를 대입
                {
                    q.push(make_pair(nh, nw));
                    //체크한 순간 cnt 는 상 하 좌 우 모두 d[h][w]+1
                    c[nh][nw] = 1;
                    d[nh][nw] = d[h][w] +1;
                }
 
        }
    }
}
 
int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            scanf("%1d", &a[i][j]);
    for(int i = 0; i< N; i++)
        for(int j = 0;j <M; j++)
            if (a[i][j] == 1 && c[i][j] == 0)//체크가 안되어 있지만 길이 있다면
            {
                BFS(i, j);
            }
    cout << d[N-1][M-1] << '\n';
}