[BOJ] 1245번_농장 관리_DFS (C++)

[문제]

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

NxM 격자로 이루어진 농장이 있는데, 이 농장을 관리하기 위해 산봉우리마다 경비원을 배치하려고 한다. 이를 위해 농장에 산봉우리가 총 몇 개 있는지 구하는 문제이다.

산봉우리의 정의는 다음과 같다. 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다.(인접하다는 것은 상하좌우뿐만아니라 대각선까지 닿아있는 경우를 뜻한다.) 또한 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 낮아야한다.

[사용 알고리즘]

(깊이 우선 탐색)

[풀이 핵심]

• 인접한 칸에 현재칸보다 높은 봉우리가 존재할 경우 현재칸은 산봉우리가 될 수 없으므로 bool타입 check변수를 활용해서 체크해준다.
• 인접한 칸에 해당 칸이랑 높이가 같은 봉우리가 존재할 경우 같은 높이를 가지는 하나의 격자의 조건을 만족할 수 있기 때문에 DFS를 통해 탐색해준다.
• 당연히 높이가 0이면 산봉우리가 될 수 없다.

[코드]

//boj1245번_농장 관리_그래프

#include<iostream>

using namespace std;

int graph[101][71];
bool visited[101][71];

int dx[8] = { 1,1,0,-1,-1,-1,0,1 };
int dy[8] = { 0,1,1,1,0,-1,-1,-1 };

int N, M;

int cnt = 0;

bool check;

void DFS(int x, int y) {
	visited[x][y] = true;

	for (int i = 0; i < 8; i++) {
		int next_x = x + dx[i];
		int next_y = y + dy[i];

		if (next_x >= 0 && next_x < N && next_y >= 0 && next_y < M && graph[x][y] < graph[next_x][next_y]) {
			check = false;
		}

		if (next_x >= 0 && next_x < N && next_y >= 0 && next_y < M && !visited[next_x][next_y]) {
			if (graph[next_x][next_y] == graph[x][y]) {
				DFS(next_x, next_y);
			}
		}
	}
}

int main() {
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> graph[i][j];
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (!visited[i][j] && graph[i][j] != 0) {
				check = true;

				DFS(i, j);

				if (check) {
					cnt++;
				}
			}
		}
	}

	cout << cnt;

	return 0;
}