[boj][c++] 2468 안전영역

강남 침수로 클러스터에 못가게 된 오늘의 상황이 떠오르는 문제를 풀었다. 어제 외출했다가 클러스터에 들릴까 생각했었는데, 들렸으면 집에 못 돌아올 뻔 했다. 사진으로만 봐도 피해가 심해보이는데 빨리 정상화되길

2468 안전 영역

문제 설명이 빈약해서 방향 잡기가 다소 난해했다. 그러나 안전 영역의 개념이 넓이가 아닌 분할 개수라는 점을 이해하면 쉽게 풀 수 있다.

n * n 영역 내에서 가장 높은 지대를 maxe라고 하면 height >= 0 && height < maxe 를 모두 돌면서 각각의 높이만큼 비가 올 때 물에 잠기지 않은 구역의 개수를 구한 뒤 그 중 가장 높은 수를 출력하면 된다.

maxe는 별도의 탐색 없이 자료를 입력받을 때 함께 구해줬다.

구하는 방식은 다른 그래프 탐색 문제와 다를 바 없음

#include	<iostream>
#include	<cstring>
#include	<algorithm>
#include	<queue>
using namespace std;

int n, maxe, cnt, ans;
int graph[101][101];
bool visit[101][101];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

void bfs(int x, int y, int d)
{
	visit[x][y] = true;
	queue<pair<int, int>>q;
	q.push({ x,y });
	while (!q.empty())
	{
		int sx = q.front().first;
		int sy = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = sx + dx[i];
			int ny = sy + dy[i];
			if ((nx >= 0 && nx < n) && (ny >= 0 && ny < n) 
            		&& visit[nx][ny] == false && graph[nx][ny] > d)
			{
				visit[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 >> graph[i][j];
			if (maxe < graph[i][j])
				maxe = graph[i][j];
		}
	}
	for (int i = 0; i < maxe; i++)
	{
		memset(visit, false, sizeof(visit));
		cnt = 0;
		for (int j = 0; j < n; j++)
		{
			for (int k = 0; k < n; k++)
			{
				if (graph[j][k] > i && visit[j][k] == false)
				{
					cnt++;
					bfs(j, k, i);
				}
			}
		}
		ans = max(ans, cnt);
	}
	cout << ans << endl;
}