백준 2178 - 미로 탐색

문제

 

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

2178번: 미로 탐색

 

 

풀이

 

bfs 탐색을 (1,1)에서 시작해서 (N,M)에 도착했을 때 지나가는 level의 수가 최소 횟수가 된다.

result = (1,1)에서 (N,M)까지 이동할 때 지나야하는 최소 칸 수 라고 할 때,

bfs 탐색을 진행하면서 현재 level에 해당되는 좌표들을 모두 방문한 후에 result 값을 증가시켜주면 된다.

 

현재 level에 해당하는 좌표를 모두 방문하려면, bfs 탐색에서 현재 큐에 저장되어 있는 데이터 수 만큼 큐에서 꺼내서 다음 방문할 좌표를 찾는 작업을 하면 된다.

 

 

코드

 

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