BOJ 2178 - 미로 탐색

문제

 

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

2178번: 미로 탐색

 

 

풀이

 

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

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

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

 

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

 

 

코드

java

#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;
}
 

 

 

python

from collections import deque
 
 
def bfs(x, y):
    cnt = 0
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
 
    q = deque([[0, 0]])
    maze[y][x] = 0
 
    while q:
        level = len(q)
        cnt += 1
        for _ in range(level):
            cur_y, cur_x = q.popleft()
 
            if cur_y == n - 1 and cur_x == m - 1:
                return cnt
 
            for i in range(4):
                next_y = cur_y + dy[i]
                next_x = cur_x + dx[i]
                if 0 <= next_y < n and 0 <= next_x < m and maze[next_y][next_x] == 1:
                    q.append([next_y, next_x])
                    maze[next_y][next_x] = 0
 
 
n, m = map(int, input().split())
maze = [list(map(int, input())) for _ in range(n)]
 
print(bfs(0, 0))
 

 

 

C++

#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;
}