BOJ 2178 - 미로탐색

20 Mar 2017 on Algorithm

출처 BOJ

미로탐색

문제

N×M크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2≤N, M≤100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제

범위체크

최대 칸 수 100x100 $\lt INT$

풀이

bfs를 사용해서 갈 수 있는 위치로 이동하고 이동한 위치에는 몇번만에 왔는지 기록
MAP[N-1][M-1]위치가 총 오는데 걸린 최단 거리가 됨

코드

code

#include<cstdio>
#include<queue>
#define BOUND 101

using namespace std;

int N, M;
int MAP[BOUND][BOUND];
queue<pair<int,int> > Q;
int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };

void searchMaze(){
	while(!Q.empty()){
		int x = Q.front().first;
		int y = Q.front().second;
		Q.pop();

		for(int t=0; t<4; t++){
			int tx = x + dir[t][0];
			int ty = y + dir[t][1];
			if(0<=tx && tx<N && 0<=ty && ty<M && MAP[tx][ty]==1){
				MAP[tx][ty] = MAP[x][y] + 1;
				Q.push(make_pair(tx,ty));
			}
		}
	}
}

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]);
	}

	Q.push(make_pair(0,0));
	MAP[0][0] = 2;

	searchMaze();

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

복잡도

$O(NM)$
각 칸을 한 번씩만 방문하므로