[백준] 2178번 미로 탐색

문제

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

풀이과정

시작점부터 이동할 수 있는 칸을 이용해서 (N,M)까지 가야한다.
주어진 칸을 최소한으로 이용하며 도착할 수 있을 때 최소 칸 수를 출력 해야한다.

기본적인 BFS 문제라고 한다. DFS로는 풀 수 없는 문제다. 문제를 풀다가 DFS와 BFS를 어떨 때 써야 좋을까 라는 생각이 들어서 검색해봤다.

DFS는 사이클 탐지, 위상정렬
BFS는 최소신장트리, 최단경로

소스코드

#include <cstdio>
#include <queue>

#pragma warning(disable:4996)

#define MAX 100

using namespace std;

int map[MAX][MAX];
int ans[MAX][MAX];
bool chk[MAX][MAX];
int N, M;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };

int main()
{
    scanf("%d %d", &N, &M);

    for (int i = 0;i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            scanf("%1d", &map[i][j]);
        }
    }

    queue<pair<int, int>> q;

    q.push(make_pair(0, 0));
    chk[0][0] = true;
    ans[0][0] = 1;

    while (!q.empty())
    {
        int x = q.front().first; int y = q.front().second;
        q.pop();
        for (int k = 0; k < 4; k++)
        {
            int nx = x + dx[k]; int ny = y + dy[k];
            if (0 <= nx && nx < N && 0 <= ny && ny < M)
            {
                if (map[nx][ny] == 1 && chk[nx][ny] == false)
                {
                    q.push(make_pair(nx, ny));
                    ans[nx][ny] = ans[x][y] + 1;
                    chk[nx][ny] = true;
                }
            }
        }
    }

    printf("%d\n", ans[N - 1][M - 1]);

    return 0;
}