[BOJ] 2468번 안전 영역 (C++)

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

2468번: 안전 영역

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <memory.h>
using namespace std;

int n, cnt;
int arr[101][101];
int fixedarr[101][101];
bool visited[101][101];
int dx[4] = { -1, 0, 0, 1 };
int dy[4] = { 0, -1, 1, 0 };

void bfs(int a, int b) {
	queue<pair<int, int>> q;
	visited[a][b] = true;
	q.push({ a, b });

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

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

			if (!(nx >= 0 && ny >= 0 && nx < n && ny < n)) continue;

			if (!visited[nx][ny] && fixedarr[nx][ny] == 1) {
				visited[nx][ny] = true;
				q.push({ nx, ny });
			}

		}
	}
}

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

	cin >> n;

	int max = -1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (max < arr[i][j]) max = arr[i][j];
		}
	}

	int ans = 0;
	for (int i = 1; i <= max; i++) {
		for (int x = 0; x < n; x++) {
			for (int y = 0; y < n; y++) {
				if (arr[x][y] < i) fixedarr[x][y] = 0;
				else fixedarr[x][y] = 1;
			}
		}

		for (int x = 0; x < n; x++) {
			for (int y = 0; y < n; y++) {
				if (fixedarr[x][y] == 1 && !visited[x][y]) {
					cnt++;
					bfs(x, y);
				}
			}
		}
		if (ans < cnt) ans = cnt;
		
		memset(visited, false, sizeof(visited));
		memset(fixedarr, 0, sizeof(fixedarr));
		cnt = 0;
	}
	cout << ans;
	return 0;
}

 

가장 높은 지점의 높이를 구하고

높이가 i(1~가장 높은 지역)이하인 지점을 모두 잠기게 만드는 비가 내린다고 할 때,

    높이가 i 미만인 지점은 0, i 이상인 지점은 1로 바꾼 임의의 배열을 만들고

    임의의 배열에서 1인 지점에 대해 bfs를 돌려 물에 잠기지 않는 영역 개수를 구한다.

1~가장 높은 지역 중 최대 영역 개수를 구한다.