Algorithm

백준 2468 : 안전 영역

쿠케캬캬 2021. 11. 20. 01:03
반응형
 

2468번: 안전 영역

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는

www.acmicpc.net

 

각 높이만큼 비가 내렸을 때, 각 경우마다 안전 영역 개수를 구해주었습니다.

 

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#define MAX 100
using namespace std;

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

int n, map[MAX][MAX], ans = 1;
int visit[MAX][MAX] = { 0 };
set<int> h;

void dfs(int x, int y, int rain) {
	visit[x][y] = rain;
	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 (visit[nx][ny] == rain || map[nx][ny] <= rain) continue;
		dfs(nx, ny, rain);
	}
}

int countSafetyZone(int rain) {
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] > rain && visit[i][j] != rain) {
				dfs(i, j, rain);
				cnt++;
			}
		}
	}
	return cnt;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &map[i][j]);
			h.insert(map[i][j]);
		}
	}

	for (int hh : h) {
		ans = max(ans, countSafetyZone(hh));
	}

	printf("%d", ans);
}
반응형