[2178] 미로 탐색

문제

N×M크기의 배열로 표현되는 미로가 있다.

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

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

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

입력

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

출력

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

코드

#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

int N, M;
int arr[101][101];
int cache[101][101];
int ans = 9999999;
int dir[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

void bfs(int x, int y){
	queue<pair<int,int>> q;
	memset(cache, 0, sizeof(cache));
	q.push({x,y});
	cache[x][y] = 1;
	
	while(!q.empty()){
		pair<int, int> here = q.front();
		q.pop();

		
		for(int i=0; i<4; ++i){
			int nx = here.first + dir[i][0];
			int ny = here.second + dir[i][1];
			if(nx == N && ny == M){
				int there = cache[here.first][here.second];
				if(cache[N][M] == 0){
					cache[N][M] = there + 1;
				}
				else{
					if(cache[N][M] > there+1){
						cache[N][M] = there+1;
					}
				}
				continue;
			}
			
			if(arr[nx][ny] == 1 && cache[nx][ny] == 0){
				q.push({nx, ny});
				cache[nx][ny] = cache[here.first][here.second] + 1;
			}
		}

		
	}
}

int main(void){
	cin >> N >> M;

	for(int i=1; i<N+1; ++i){
		for(int j=1; j<M+1; ++j){
			scanf("%1d", &arr[i][j]);
		}
	}

	bfs(1, 1);

	cout << cache[N][M];
	
	return 0;
}

이 문제는 BFS + 유사 dp 를 활용해서 풀었다.

bfs는 위에서부터 하나하나씩 차근차근 내려오기 때문에 최적해를 찾을 수 있다.

이 문제의 경우 dfs를 찾으면 경로가 아주 많을 수 있어 시간복잡도가 커질수 있지만 bfs는 최단거리(최적해)에 유용하기 때문에 bfs를 활용해 주었다.

또한 최소값을 찾아주는 문제이기 때문에 cache를 활용해서 dp라기엔 애매하지만 각 위치마다 이동한 값을 저장시켜 가장 최소값을 구해주었다.

dfs와 bfs를 사용하는 경우를 잘 파악해야 된다.

 

bfs는 최단거리를 찾을 때 유용하다!!