[BOJ] 2178. 미로 탐색

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

2178번: 미로 탐색

이 문제는 (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제이다.

문제에서는 1, 1이라고 한 곳은 실제로는 0, 0 이므로 주의해야 한다!

마찬가지로 마지막 칸 N, M도 (N-1, M-1) 칸을 출력해주면 된다.

 

최소 칸수를 구하는 문제이므로 bfs를 사용한다.

시작칸에서 부터 갈 수 있는 칸으로 단계적으로 진행하기 때문에 최단 거리로 이동할 수 있다.

이동할 때마다 각 칸에는 해당 칸까지의 이동 횟수를 저장해준다.

그러면 최종적으로 마지막 칸에 마지막 칸까지의 최소 이동 횟수가 저장된다.

 

 

문제에 나와있는 예시를 보면 아래와 같이 지도가 있는데

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

 

bfs를 통해 이동 횟수를 cnt배열에 저장해주면 다음과 같다.

1	0	9	10	11	12
2	0	8	0	12	0
3	0	7	0	13	14
4	5	6	0	14	15

 

#include <cstdio>
#include <queue>
using namespace std;
 
int n,m;
int map[100][100];
int cnt[100][100];
int dx[] = {0,0,1,-1};
int dy[] = {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));
    cnt[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(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if(map[nx][ny] == 1 && cnt[nx][ny] == 0) {
                q.push(make_pair(nx,ny));
 
                //이전 단계보다 1 증가(이동 횟수 증가)
                cnt[nx][ny] = cnt[x][y] + 1;
            }
        }
    }
 
    //마지막 칸을 출력
    printf("%d\n", cnt[n-1][m-1]);
 
    return 0;
}