[알고리즘] 백준 2178번: 미로탐색(C++), DFS와 BFS의 차이

이번 문제는 DFS를 활용하여 풀려했었다. 하지만, DFS로 구현할 경우에는 TLE가 발생한다.

게시판에서는 BFS를 활용하여 풀어야 한다고 조언한다.

 

---

문제를 풀 때 어떤 포인트에서 DFS 혹은 BFS로 풀어야 하는지 알 수 있을까?

여러 블로그를 읽어보다가 감이 잡힌 듯하다.
최단 경로를 알아보아야 할 때, BFS
BFS는 어떤 기준점으로부터 인접한 노드들을 차근차근 접근 해나가지만 DFS는 한 군데 길로 쭉 갔다가 조건을 만족하지 못하면 다시 돌아와 다른 노드들을 접근하기 때문에 시간적인 측면에서 BFS가 이런 부분에서는 효율적이다.
하지만, 경로에 대해 가중치(weight)가 붙을 때는 DFS를 활용해야 한다.
이동 과정에 있어서 여러 제약이 있을 때는 DFS (이 점에서 백트래킹과 유사한 거 같다.)

 

(+참고)

https://na0dev.tistory.com/32

BFS & DFS 문제 구분

https://haams704.tistory.com/75

BFS & DFS 구분하자!

https://velog.io/@ming/DFS-vs-BFS-%ED%83%90%EC%83%89

DFS vs BFS 탐색

 

아무리 어떨 때 무엇을 써야 한다고를 들었다 한들 직접 겪어보면서 풀어나가야 할 거 같다.

---

DFS를 활용한 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n, m;
vector<int> answer;

typedef struct {
	int y, x;
} Direction;

Direction dir[4] = { {-1,0},{1,0},{0,-1},{0,1} };//up,down,left,right

void sol(vector<vector<int>>& arr, int row, int col, int cnt) {
	if (row == n && col == m) {
		answer.push_back(cnt);
		return;
	}

	for (int i = 0; i < 4; i++) {
		int nextY = row + dir[i].y;
		int nextX = col + dir[i].x;

		if (nextY >= 1 && nextY <= n && nextX >= 1 && nextX <= m && arr[nextY][nextX] == 1) {
			arr[nextY][nextX] = 0;
			sol(arr, nextY, nextX, cnt + 1);
			arr[nextY][nextX] = 1;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;
	vector<vector<int>> arr(n + 1, vector<int>(m + 1, 0));

	for (int i = 1; i <= n; i++) {
		string a;
		cin >> a;
		for (int j = 1; j <= m; j++) {
			arr[i][j] = a[j - 1] - '0';
		}
	}
	
	arr[1][1] = 0;

	sol(arr, 1, 1, 1);

	sort(answer.begin(), answer.end());
	cout << answer[0];
	return 0;
}

이럴 경우 그래프 크기가 100 * 100 일 때, 최악의 경우에는 한 노드에서 4가지 방향을 고르는데 4^(100 * 100) 정도 걸린다고 하면 엄청난 시간이 걸리게 된다.



그래서, BFS를 활용했다.

>> BFS는 큐를 이용한다. 이 원리에 대해서는 나중에 포스팅하고 싶다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <utility>
using namespace std;

int n, m;
vector<int> answer;
queue<pair<int, int>> idx;
bool visited[101][101] = { 0, };
int length[101][101] = { 0, };

typedef struct {
	int y, x;
} Direction;

Direction dir[4] = { {-1,0},{1,0},{0,-1},{0,1} };//up,down,left,right

void sol(vector<vector<int>>& arr, int row, int col) {
	idx.push(make_pair(row, col));
	length[row][col] = 1;

	while (!idx.empty()) {
		int y = idx.front().first;
		int x = idx.front().second;

		idx.pop();

		for (int i = 0; i < 4; i++) {
			int nextY = y + dir[i].y;
			int nextX = x + dir[i].x;

			if (nextY >= 1 && nextY <= n && nextX >= 1 && nextX <= m && arr[nextY][nextX] == 1 
				&& visited[nextY][nextX] == 0) {
				arr[nextY][nextX] = 0;
				visited[nextY][nextX] = 1;
				length[nextY][nextX] = length[y][x] + 1;
				idx.push(make_pair(nextY, nextX));

			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;
	vector<vector<int>> arr(n + 1, vector<int>(m + 1, 0));

	for (int i = 1; i <= n; i++) {
		string a;
		cin >> a;
		for (int j = 1; j <= m; j++) {
			arr[i][j] = a[j - 1] - '0';
		}
	}

	arr[1][1] = 0;

	sol(arr, 1, 1);

	cout << length[n][m];
	return 0;
}

---

DFS, BFS를 구분할 줄 아는 안목이 필요하다.