[백준][C++] 2468: 안전 영역

문제 링크: https://www.acmicpc.net/problem/2468

 

적당히 bfs 또는 dfs로 영역 수 세주면 됩니다

#include <bits/stdc++.h>
using namespace std;


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

int n;
int height[100][100];
int mask[100][100];
int max_areas;
int max_height;


inline bool in_range(int y, int x) {
	return y >= 0 && y < n&& x >= 0 && x < n;
}

void dfs(int y, int x) {
	mask[y][x] = 1;

	for (int i = 0; i < 4; ++i) {
		auto ny = y + dy[i];
		auto nx = x + dx[i];

		if (in_range(ny, nx) && mask[ny][nx] == 0) {
			dfs(ny, nx);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	cin >> n;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j) {
			cin >> height[i][j];
			max_height = max(max_height, height[i][j]);
		}

	for (int h = 0; h <= max_height; ++h) {
		int area_cnt = 0;

		memset(mask, 0, sizeof(mask));
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < n; ++j)
				if (height[i][j] <= h)
					mask[i][j] = 1;

		for (int i=0; i<n; ++i)
			for (int j=0; j<n; ++j)
				if (mask[i][j] == 0) {
					++area_cnt;
					dfs(i, j);
				}

		max_areas = max(max_areas, area_cnt);
	}
	cout << max_areas << '\n';

	return 0;
}

mask라는 배열을 만들어놓고 영역마다 dfs를 돌렸습니다

물이 차지 않는다는 점도 문제에 써있으니 물 차는 높이 h는 [0, max_height]로 하면 될듯 합니다