[C++]BOJ 2178 - 미로 탐색

각 칸에서 이동할 수 있는 칸으로 탐색해나가 도착점에 도달하면 그 이동 거리가 최소 거리가 되므로 bfs를 사용하면 빠르게 해결할 수 있다.
dfs로도 해결할 수 있지만 한번 방문한 칸은 다신 방문하지 않는 bfs와는 다르게 모든 경로를 탐색하므로 작동시간이 다소 오래걸린다.

두 방법 모두 다뤄보겠다.

우선 bfs를 사용한 방법은 x, y방향, 이동횟수 큐를 만들어서 각각 1을 넣어준다. (시작점 좌표(1, 1), 시작 이동횟수 = 1)
이후 상하좌우로 이동할 수 있는 칸을 큐에 계속 넣어주고 이동횟수도 업데이트한다.
큐가 비었거나 도착점에 도달하면 종료 후 이동횟수를 출력한다.

#include <iostream>
#include <queue>
using namespace std;
queue<int> qx, qy, qc;
int n, m, arr[101][101], v[101][101], sx, sy, sc, ans;
bool chk(int x, int y) {
	if(x > m || x < 1 || y > n || y < 1) return false;
	if(!arr[y][x]) return false;
	if(v[y][x]) return false;
	return true;
}
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			scanf("%1d", &arr[i][j]);
	qx.push(1), qy.push(1), qc.push(1);
	while(!qx.empty()) {
		sx = qx.front(); qx.pop();
		sy = qy.front(); qy.pop();
		sc = qc.front(); qc.pop();
		if(v[sy][sx]) continue;
		v[sy][sx] = 1;
		if(sx == m && sy == n) break;
		if(chk(sx - 1, sy)) qx.push(sx - 1), qy.push(sy), qc.push(sc + 1);
		if(chk(sx + 1, sy)) qx.push(sx + 1), qy.push(sy), qc.push(sc + 1);
		if(chk(sx, sy - 1)) qx.push(sx), qy.push(sy - 1), qc.push(sc + 1);
		if(chk(sx, sy + 1)) qx.push(sx), qy.push(sy + 1), qc.push(sc + 1);
	}
	cout << sc;
}

dfs를 사용한 방법은 앞서 설명한 bfs보다 간단하다.
이동할 수 있는 모든 칸을 찾으며 각 칸까지 도달하는데 최소 이동횟수를 저장한다.
도착점에 저장된 이동횟수를 출력한다.
모든 경우를 탐색하므로 시간이 오래 걸린다.

#include <iostream>
using namespace std;
int n, m, arr[101][101], ans[101][101];
void dfs(int x, int y, int cnt) {
	if(!arr[y][x]) return;
	if(x < 1 || y < 1 || x > m || y > n) return;
	if(ans[y][x] <= cnt && ans[y][x]) return;
	ans[y][x] = cnt;
	dfs(x - 1, y, cnt + 1);
	dfs(x + 1, y, cnt + 1);
	dfs(x, y - 1, cnt + 1);
	dfs(x, y + 1, cnt + 1);
}
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			scanf("%1d", &arr[i][j]);
	dfs(1, 1, 1);
	cout << ans[n][m];
}