미로 탐색 (feat. 백준, 2178번)

미로 탐색
https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
int N, M, dx[4], dy[4], arr[100][100];
bool visit[100][100];
void dfs(register int x, register int y) {
	if (x == N - 1 && y == M - 1)		return;
	visit[x][y] = true;
	for (register int d = 0, nx, ny; d < 4; ++d) {
		nx = x + dx[d], ny = y + dy[d];
		if (0 <= nx && nx < N && 0 <= ny && ny < M && !visit[nx][ny] && arr[nx][ny] != 0)
			arr[nx][ny] = arr[x][y] + 1, dfs(nx, ny);
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
	dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
	cin >> N >> M;
	char tmp;
	for (register int n = 0, m; n < N; ++n)
		for (m = 0; m < M; ++m)
			cin >> tmp, arr[n][m] = tmp - '0', visit[n][m] = false;
	dfs(0, 0);
	cout << arr[N - 1][M - 1];
	return 0;
}
// *&)*@*

DFS 풀이 방법

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int N, M, dx[4], dy[4], arr[100][100];
bool visit[100][100];
void bfs(register int x, register int y) {
	visit[x][y] = true;
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	while (!q.empty()) {
		auto v = q.front(); q.pop();
		x = v.first, y = v.second;
		for (register int d = 0, nx, ny; d < 4; ++d) {
			nx = x + dx[d], ny = y + dy[d];
			if (0 <= nx && nx < N && 0 <= ny && ny < M && !visit[nx][ny] && arr[nx][ny] != 0)
				arr[nx][ny] = arr[x][y] + 1, visit[nx][ny] = true, q.push(make_pair(nx, ny));
		}
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
	dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
	cin >> N >> M;
	char tmp;
	for (register int n = 0, m; n < N; ++n)
		for (m = 0; m < M; ++m)
			cin >> tmp, arr[n][m] = tmp - '0', visit[n][m] = false;
	bfs(0, 0);
	cout << arr[N - 1][M - 1];
	return 0;
}
// *&)*@*

BFS 풀이 방법

 

1. 가장 빠르게 가는 방법과 같은 문제는 DFS로 풀이하기에는 까다롭거나 효율이 월등하게 떨어집니다. (불가능하진 않습니다.)
2. 왜냐하면 BFS의 경우, 하나의 위치에서 퍼져나가는 방법으로 풀이를 하지만 DFS의 경우, 하나의 방향에 대해서 모든 해를 풀고 다음 방향은 다음번에 해를 구하는 방식이기 때문입니다.
3. 따라서 위의 풀이 방법 중 DFS는 올바른 답을 도출할 수 없습니다.
4. 만약 DFS로 풀이한다면 해당 지점을 체크했다는 flag 변수를 사용하지 않아야 합니다.