#2468. 안전 영역

Problem

• 문제링크

Solution

1. 높이 1부터 최대 높이까지 작업을 진행한다. → set에 높이 정보를 담고 오름차순으로 정렬하면 더 빠를듯
2. 각 높이마다 모든 영역을 탐색한다. (말이 모든 영역이지 이미 높이보다 같거나 작은 영역이나 방문한 영역이면 탐색을 하지 않는다.)
   탐색은 BFS로 안전영역을 표시한다.
3. 탐색이 끝나면 안전 영역의 수를 1증가한다.

1 Try

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int N, max_height, ans = 1;
int arr[100][100];
bool visited[100][100];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
void BFS(int x, int y, int h) {
	queue<pair<int, int>> q;
	q.push({ x, y });
	visited[x][y] = true;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int dir = 0; dir < 4; ++dir) {
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
			if (visited[nx][ny] || arr[nx][ny] <= h) continue;
			visited[nx][ny] = true;
			q.push({ nx, ny });
		}
	}
}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			cin >> arr[i][j];
			if (max_height < arr[i][j]) max_height = arr[i][j];
		}
	}
	for (int h = 1; h <= max_height; ++h) {
		int area = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (visited[i][j] || arr[i][j] <= h) continue;
				BFS(i, j, h);
				area++;
			}
		}
		if (ans < area) ans = area;
		memset(visited, false, sizeof(visited));
	}
	cout << ans << "\n";
	return 0;
}