[백준 / #2178 / C++] 미로 탐색

오늘은 백준 2178번 문제인 미로 탐색 문제를 보자.

 

알고리즘 공부를 하면서 어떤 가이드라인을 보면서 하는 것은 아니기 때문에 항상 오늘 풀 문제를 선정하는데 있어 고민이

 

많이 된다. 알고리즘은 학교 수업을 들은 것이 다이다...(문제해결기법..어려웠따..) 이번 문제는 solved.ac를 떠돌며 보던 중

 

실버1 문제 중에 제일 사람들이 많이 푼 문제여서 이거다! 싶어서 풀었다.

 

 

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

2178번: 미로 탐색

 

처음에는 문제를 보자마자 떠올랐다. 재귀를 통해 깊이우선탐색(DFS)을 구현하였고 대차게 시간초과가 나버렸다! 이런!!! 

 

그래서 코드를 다시 살펴봤지만 내가 새로 떠올린 것으로 해봤지만 역시나 또 다시 시간초과가 났기 때문에 새로운 방법을

 

찾아 떠났다. 밑에 코드는 시간초과가 난 코드이다.

 

#include <iostream>
#include <vector>
#include <string>

using namespace std;
vector<string> maze;
int ans[1] = { 20000000 };
int n, m;

void path(int y, int x, int temp) {
	if (y == n - 1 && x == m - 1) {
		if(temp < ans[0])
			ans[0] = temp;
	}
	else {
		if (y < n - 1) {
			if (maze[y + 1][x] == '1') {
				maze[y].replace(x, 1, "0");
				path(y + 1, x, temp + 1);
				maze[y].replace(x, 1, "1");
			}
		}
		if (x < m - 1) {
			if (maze[y][x + 1] == '1') {
				maze[y].replace(x, 1, "0");
				path(y, x + 1, temp + 1);
				maze[y].replace(x, 1, "1");
			}
		}
		if (y > 0) {
			if (maze[y - 1][x] == '1') {
				maze[y].replace(x, 1, "0");
				path(y - 1, x, temp + 1);
				maze[y].replace(x, 1, "1");
			}
		}
		if (x > 0) {
			if (maze[y][x - 1] == '1') {
				maze[y].replace(x, 1, "0");
				path(y, x - 1, temp + 1);
				maze[y].replace(x, 1, "1");
			}
		}
	}
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		string tmp;
		cin >> tmp;
		maze.push_back(tmp);
	}

	path(0, 0, 1);

	cout << ans[0];

	return 0;
}

경로를 지워가며 탐색해서 따로 방문 여부를 배열로 찾을 필요가 없었고 재귀로 돌아오게 되면 다른 탐색을 위해 경로를 복

 

구해주는 알고리즘이었다. (재귀의 기본! 다시 복구시켜주기 잊지 마세요!)

 

 

 

그렇게 계속 생각하다가 최단경로에 꽂혀 다시 생각해본 결과 이 문제는 DFS가 아닌 넓이우선탐색(BFS)로 푸는 문

 

제였다. 그렇게 나온 넓이우선탐색(BFS) 알고리즘을 밑에서 확인해보자.

 

 

코드는 위와 같다. 마찬가지로 문제에서 말했듯이 미로는 모두 붙어서 주어지기 때문에 문자의 형태로 생각했고 각각 char

 

형으로 입력을 받으면 손쉽게 분리가 가능하다. 이렇게 분리한 경로들을 사용하여 BFS에 넣고 돌린다. 여기서 조금은 특이

 

한 점은 x와 y좌표를 사용했다는 것이다. 일종의 내 습관인데 x, y 좌표가 나오면 보통은 pair를 통해 나타내려고 하는 편이

 

다. x와 y 좌표를 이용하여 BFS를 펼치며 방문한 좌표는 이미 방문했다는 의미해서 경로를 삭제해주었다. 이렇게 해야 그 

 

다음 노드에서 탐색이 되지 않는다.

 

 

여기서 1가지 의문점이 들 수 있는데 왜 각 좌표까지 방문한 경로의 최솟값으로 놓지 않고 그냥 저렇게 무턱대고 저장해버

 

리면 어쩌지? 라는 생각을 할 수 있다. 나도 코드를 짜며 처음에는 값을 비교하며 최솟값을 저장하려고 했지만 코드를 치던

 

도중 필요가 없는 일이라는 것을 깨달았다. 어차피 BFS를 통해 값을 저장하게되면 경로가 삭제될 것이고, 만약 이미 경로

 

가 삭제되었다면 지금 방문보다 더 전에 방문하였다는 의미이고, 이는 곧 최솟값이라는 말이기 때문이다. (그리고 어차피

 

경로가 삭제됐기 때문에 계산 또한 실행되지 않는다.) 이 부분이 나름 핵심이라고 생각했다.

 

 

그렇게 BFS를 한 번만 돌리고 나면 마지막 (m, n) 배열에는 최솟값이 기록되고 이것을 출력하면 답이다!

 

 

이렇게 너비우선탐색(BFS)를 활용한 문제를 살펴보았는데 문제가 생각보다 너무 좋아서 만족했다 ㅎㅎ

 

언젠가는 너비우선탐색에 대해서도 다뤄봐야겠다.