백준 2178번 - 미로 탐색

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

2178번: 미로 탐색

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

int n, m; //미로의 행(n), 열(m)의 수
int map[101][101]; //미로 map
int result[101][101]; //탐색 결과
queue<pair<int, int>> Q;
// 이동 경로에 대한 좌표값(상, 하, 우, 좌)
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

void BFS(int x, int y, int value)
{
    Q.push(make_pair(x, y)); //초기 위치를 Queue에 입력
    result[x][y] = value;
    while (!Q.empty())
    {
        x = Q.front().first;
        y = Q.front().second;
        Q.pop();

        for (int i = 0; i < 4; i++)
        {

            int nx = x + dx[i];
            int ny = y + dy[i];

            if (0 <= nx && nx < n && 0 <= ny && ny < m)
            {
                if (map[nx][ny] == 1 && result[nx][ny] == 0)
                {
                    Q.push(make_pair(nx, ny));
                    result[nx][ny] = result[x][y] + 1;
                }
                if (map[nx][ny] == 1 && result[nx][ny] != 0)
                {
                    result[nx][ny] = min(result[nx][ny], result[x][y] + 1);
                }
            }
        }
    }
}

int main(int argc, char* argv[])
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        	//미로의 이동 가능 경로 정보를 입력
            scanf("%1d", &map[i][j]);
    }

    BFS(0, 0, 1);

    printf("%d\n", result[n - 1][m - 1]);
    return 0;
}