[C++] 백준 2178 미로 탐색

 
#include <iostream>
#include <string.h>
#include <queue>
#include <tuple>
 
int graph[101][101] = {};
bool visit[101][101] = {};
int DirX[4] = { 1, -1, 0, 0 };
int DirY[4] = { 0, 0, 1, -1 };
 
int main()
{
    int N = 0;
    int M = 0;
 
    std::cin >> N >> M;
 
    for (int i = 0; i < N; ++i)
    {
        std::string sNumber = {};
        std::cin >> sNumber;
 
        for (int j = 0; j < M; ++j)
        {
            graph[i][j] = sNumber[j] - '0';
        }
    }
 
    std::queue<std::tuple<int, int, int>> que = {};
    que.push({1, 0,0});
 
    while (!que.empty())
    {
        std::tuple<int, int, int> top = que.front();
        int iCount = std::get<0>(top);
        int iX = std::get<1>(top);
        int iY = std::get<2>(top);
        que.pop();
 
        visit[iX][iY] = true;
 
        for (int i = 0; i < 4; ++i)
        {
            int iNextX = iX + DirX[i];
            int iNextY = iY + DirY[i];
 
            if (iNextX >= 0 && iNextX < N &&
                iNextY >= 0 && iNextY < M)
            {
                if (graph[iNextX][iNextY] == 1 && !visit[iNextX][iNextY])
                {
                    graph[iNextX][iNextY] = iCount + 1;
                    que.push({ iCount +1,iNextX, iNextY });
                }
                else if (!graph[iNextX][iNextY])
                    continue;
                else if (graph[iNextX][iNextY] <= graph[iX][iY] && !visit[iNextX][iNextY])
                {
                    graph[iNextX][iNextY] = iCount + 1;
                    que.push({ iCount + 1, iNextX, iNextY });
                }
            }
        }
    }
 
    if (graph[N - 1][M - 1] == 0)
        std::cout << -1;
    else
        std::cout << graph[N - 1][M - 1];
 
    return 0;
}
 

BFS로 계산하면서 하기!