백준 2178 - 미로 탐색

문제

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

2178번: 미로 탐색

 

풀이

bfs 탐색을 이용하여 (1,1) 에서 (N, M) 까지의 거리를 알아내면 된다. bfs 탐색을 할 때는 큐에 집어넣을 때 방문했다고 설정해야한다. 만약 큐에서 꺼낼 때 방문했다고 설정하면 중복해서 큐에 들어가는 좌표가 생길 수 있다(그래서 메모리 초과가 일어났다). bfs 탐색의 level이 바뀔 때 마다 result 값을 증가시킨다.

 

코드

#include <iostream>
#include <queue>
using namespace std;
 
bool graph[102][102];
char maze[101][101];
int N, M;
int result = 1;
queue<pair<int, int>> q;
 
void findMin(int i, int j)
{
    graph[i][j] = false;
 
    if (graph[i - 1][j])
    {
        q.push(make_pair(i - 1, j));
        graph[i - 1][j] = false;
    }
    if (graph[i + 1][j])
    {
        q.push(make_pair(i + 1, j));
        graph[i + 1][j] = false;
    }
    if (graph[i][j - 1])
    {
        q.push(make_pair(i, j - 1));
        graph[i][j - 1] = false;
    }
    if (graph[i][j + 1])
    {
        q.push(make_pair(i, j + 1));
        graph[i][j + 1] = false;
    }
 
    while (!q.empty())
    {
        int len = q.size();
 
        for (int x = 0; x < len; x++)
        {
            i = q.front().first; j = q.front().second; q.pop();
            if (i == N && j == M)
            {
                result++;
                return;
            }
 
            if (graph[i - 1][j])
            {
                q.push(make_pair(i - 1, j));
                graph[i - 1][j] = false;
            }
            if (graph[i + 1][j])
            {
                q.push(make_pair(i + 1, j));
                graph[i + 1][j] = false;
            }
            if (graph[i][j - 1])
            {
                q.push(make_pair(i, j - 1));
                graph[i][j - 1] = false;
            }
            if (graph[i][j + 1])
            {
                q.push(make_pair(i, j + 1));
                graph[i][j + 1] = false;
            }
        }
        result++;
    }
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> N >> M;
 
    for (int i = 1; i <= N; i++)
        cin >> maze[i];
 
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            if (maze[i][j - 1] - '0') graph[i][j] = true;
        }
    }
 
    findMin(1, 1);
    cout << result;
 
    return 0;
}