[알고리즘] 백준 1245번: 농장 관리 (C++), DFS의 논리 접근법 -> 필터링

이번 문제는 꽤나 어려웠다.

어려웠던 포인트들을 정리해보면

1. DFS로 풀어야 할지 BFS로 풀어야 할지를 아직 헷갈린다.
2. DFS로 풀어야 할 땐 동작원리를 알고 있어도 어떠한 논리로 접근해야 하는지 모르겠다.

이번 문제는 BFS로 첫 시도를 했었다.

높이가 낮아지다가 다시 높아지는 시점을 두고 이를 경계선이라고 생각하며 구역을 나누어 각 구역을 산봉우리로 취급하려 했었다.

하지만, 이를 표현하는 데에 있어서 산 중턱에서 BFS가 돼버리면 구하려는 구역 이상의 수가 도출되기 때문에 다음 코드로는 답을 도출해낼 수 없었다.

그래서, flag 변수나 min값을 도입해 봤지만 풀리지 않았다.

#include <iostream>
#include <queue>
#include <utility>
using namespace std;

int n, m;
int map[101][71] = { 0, };
bool visited[101][71] = { 0, };
bool flag = 1;

typedef struct {
	int y, x;
} Direction;

Direction dir[8] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {1, 1}, {-1, 1}, {1, -1} };

void bfs(int row, int col, int min) {
	queue<pair<int, int>> q;
	q.push(make_pair(row, col));

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

		q.pop();
		for (int i = 0; i < 8; i++) {
			int dy = y + dir[i].y;
			int dx = x + dir[i].x;
			if (dy >= 1 && dy <= n && dx >= 1 && dx <= m) {
				if (map[dy][dx] > map[y][x]) {
					if (map[y][x] == min) {
						return;
					}
					flag = 0;
					return;
				}

				if (!visited[dy][dx]) {
					visited[dy][dx] = 1;
					q.push(make_pair(dy, dx));
				}
			}
		}
	}
}

int main() {
	cin >> n >> m;
	
	int min = 100000;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int idx;
			cin >> idx;
			map[i][j] = idx;
			if (idx < min) {
				min = idx;
			}
		}
	}

	int cnt = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (!visited[i][j]) {
				flag = 1;
				visited[i][j] = 1;
				bfs(i, j, min);

				if (flag == 1) {
					cnt++;
				}
			}
		}
	}

	cout << cnt;
	return 0;
}

---

왜 DFS로 풀어야 할까

늘 그래프 문제를 풀면서 DFS를 사용해야 풀릴 거 같다는 생각, 즉 접근법을 한 번도 가져본 적이 없었다.

BFS 문제들을 자주 풀어서인지 접근할 수 있었던 생각이 없었던 건지 DFS 문제를 자주 풀어야 할 필요를 느낀다.

 

그렇다면 '왜 BFS로 접근을 했냐'는 아무래도 문제들을 풀어오면서 혹은 알고리즘 개념들을 공부하면서 DFS와 BFS 사이에 차이를 느낀 부분이 DFS는 직선, 한 가지 길, 뾰족함 등과 같은 두루뭉술한 느낌을 주는 한 편 BFS는 구역, 한 번에 여러 가지 길, 둥근 등과 같은 두루뭉술한 느낌을 주기 때문이다.

 

알고리즘을 푸는 데에 있어서 두루뭉술하고 확실한 근거가 없는 말은 사실 최악이라고 생각한다.

하지만, 그간에 공부를 하는 데에 있어서 이보다 알고리즘에 대해 확실한 느낌을 주는 생각들이 없었기 때문에 머리에 자리를 잡았다고 생각한다.

 

논리에 있어서도 BFS라는 편협한 사고방식 때문에 생각해보지 못했던 논리였다. DFS를 더 공부해보면 이런 논리들을 쉽게 떠올릴 수 있지 않을까?

 

이번 문제 포인트는 필터링이다. DFS는 이러한 점에서 백트래킹과 유사한 점이 한 가지 더 있다. 하지만, 이번 필터링은 꽤 어려웠음을 알 수 있다.

 

예전부터 생각한 그대로다. 알고리즘은 늘 편견을 깬다. 이번 문제도 그렇다.

늘 스스로에게 고정관념을 깰 수 있는 판단력을 챙겨줘야 한다.

DFS로도 구역별로 탐색을 할 수 있었음을 참고를 통해 알 수 있었다.

(+참고 링크 https://kangminjun.tistory.com/entry/BOJ-1245%EB%B2%88-%EB%86%8D%EC%9E%A5-%EA%B4%80%EB%A6%AC)

 

---

소스 코드

DFS로 8가지 방향을 고려하며 이번 문제의 포인트는 필터링과 그 필터링 사이의 관계였다고 생각한다.

각 필터링에 대해서는 코드에 주석을 달아두었다.

#include <iostream>
#include <queue>
#include <utility>
using namespace std;

int n, m;
int map[101][71] = { 0, };
bool visited[101][71] = { 0, };
bool flag = 1;

typedef struct {
	int y, x;
} Direction;

Direction dir[8] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {1, 1}, {-1, 1}, {1, -1} };

void dfs(int row, int col) {
	for (int i = 0; i < 8; i++) { // 8가지 방향 모두 고려
		int dy = row + dir[i].y;
		int dx = col + dir[i].x;

		// 1번째 필터링
		if (dy < 1 || dy > n || dx < 1 || dx > m) { // map을 벗어나는 예외의 경우
			continue;
		}
		// 2번째 필터링
		if (map[row][col] < map[dy][dx]) { // 현재 위치에서 더 높은 곳이 있는가
			flag = 0;
		}
		// 3번째 필터링
		if (visited[dy][dx] || map[dy][dx] != map[row][col]) { // 이미 방문했던 곳인가 
							//혹은 현재 있는 곳보다 탐색하려는 곳이 현재 있는 곳보다 작은가
			continue;
		}
		// 탐색하려는 위치의 높이가 같다면 방문체크하고 dfs하라
		// dfs를 한다고 해서 산봉우리라고 착각하지 않는 이유는
		// 2번째 필터링에서 flag변수가 0이로 변환되었기 때문이다.
		visited[dy][dx] = 1;
		dfs(dy, dx);
	}
}

int main() {
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int idx;
			cin >> idx;
			map[i][j] = idx;
		}
	}

	int cnt = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (!visited[i][j]) {
				flag = 1;
				visited[i][j] = 1;
				dfs(i, j);

				if (flag == 1) {
					cnt++;
				}
			}
		}
	}

	cout << cnt;
	return 0;
}