BOJ : 2468 안전 영역

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다). 

또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다. 

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다. 

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

 

[BOJ 2468(S1) 리뷰]

 

N*N개의 건물이 주어지고 건물의 높이는 1~100사이이다.

만약 5만큼의 비가 온다면 높이가 5이하인 건물은 물에 잠기게 된다.

이 때 물에 잠기지 않은 건물들이 연결어 있는 영역이 몇개가 존재하는지 구해야한다.

비는 1~100사이의 값에서 랜덤으로 내리며 비가 내렸을때 연결되는 영역이 가장 큰 경우일 때 그 영역의 수를 구하는 문제이다.

 

처음엔 효율성을 생각하고 어렵게 생각했더니 풀이가 떠오르지 않았다.

그러나 입력값이 1~100사이므로 O(n^3)으로 코드를 작성해도 시간초과가 나지 않음을 확인하고 그냥 완전탐색을 수행했다. 비가 올수있는 최대값부터 최소값까지 반복을 하며 영역을 구하여 우선순위 큐에 넣어 집어놓고 가장 크기가 큰 값을 출력하였다.

 

#include <iostream>
#include <algorithm>
#include <list>
#include <string>
#include <vector>
#include <stack>
#include <utility>
#include <queue>
#include <deque>
#include <tuple>
using namespace std;

#define X first
#define Y second
int board[102][102];
int check[102][102];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1,  0, -1 };
priority_queue <int, vector<int>, less<int>> maxRain;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	int n;
	int rain = 100;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> board[i][j];
		}
	}
	
	while (rain>=0)
	{
		for (int i = 0; i < n; i++) //초기화
			fill(check[i], check[i] + n, 0);

		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (board[i][j] <= rain)
					check[i][j] = -1; //물에 잠긴지역을 표시.
			}
		}
		queue <pair<int, int>> Q;
		int area = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (check[i][j] != 0) continue;
				Q.push({ i,j });
				check[i][j] = 1;
				area++;
				while (!Q.empty())
				{
					auto cur = Q.front();
					Q.pop();
					for (int dir = 0; dir < 4; dir++)
					{
						int nx = cur.X + dx[dir];
						int ny = cur.Y + dy[dir];
						if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
						if (check[nx][ny] != 0) continue;
						Q.push({ nx,ny });
						check[nx][ny] = 1;
					}
				}
			}
		}
		maxRain.push(area);
		rain--;
	}

	cout << maxRain.top() << endl;
	


}