[C++]BOJ 2468 - 안전 영역

범위가 그리 크지 않기 때문에 내리는 비의 양을 완전탐색하고 그때마다 높이를 기준으로 dfs나 bfs를 돌리면 된다.
이 문제는 dfs로 풀어봤다.

#include <iostream>
#include <cstring>
using namespace std;
int n, m, h, arr[102][102], v[102][102], xx, yy, ans, tmp, dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
void dfs(int x, int y) {
	v[y][x] = 1;
	for(int i = 0; i < 4; i++) {
		xx = x + dx[i]; yy = y + dy[i];
		if(xx > n || yy > n || xx < 1 || yy < 1 || arr[yy][xx] <= h || v[yy][xx]) continue;
		dfs(xx, yy);
	}
}
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++) {
			cin >> arr[i][j];
			m = max(m, arr[i][j]);
		}
	for(h = 0; h <= m; h++) {
		memset(v, 0, sizeof(v)); tmp = 0;
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				if(arr[i][j] > h && !v[i][j]) {
					dfs(j, i);
					tmp++;
				}
		ans = max(ans, tmp);
	}
	cout << ans;
}