2468번: 안전 영역

Memo

• 침수 높이를 1부터 100까지 증가시켜갑니다.
• 높이에 따라 침수되는 함수를 작성합니다. 이때 값을 저장해 놓을 필요가 없는데, 증가시켜가기 때문에 현재 침수 높이는 앞으로 높아질 것들 중의 최소이기 때문입니다.
• 모든 점을 조사해가며 침수되지 않은 곳 부터 붙어있는 곳을 bfs로 탐색하는데, 탐색 후에는 모두 방문 처리가 되어 그 곳을 같은 높이 내에서는 다시는 방문하지 않습니다. 따라서 영역의 갯수를 구할 수 있습니다.

Code

제출 날짜

2021/03/18

메모리

2068 KB

시간

20 ms

#include <iostream>
#include <queue>
#include <algorithm>
#include <string.h>

int N;
int height[102][102];
bool visited[102][102];
std::queue<std::pair<int,int> > q;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int ans;

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	input_faster();
	std::cin >> N;
	for (int i = 0 ; i < N ; i++)
		for (int j = 0 ; j < N ; j++)
			std::cin >> height[i][j];
	ans = 1;
}

bool bfs(int b_height)
{
	int x, y, q_x, q_y, cnt;

	cnt = 0;
	memset(visited, 0, sizeof(visited));
	q = std::queue<std::pair<int, int> >();

	for(int i = 0 ; i < N ; i++)
	{
		for (int j = 0 ; j < N ; j++)
		{
			if (visited[i][j] || height[i][j] <= b_height)
				continue;
			cnt++;
			q.push({i, j});
			visited[i][j] = 1;
			while(!q.empty())
			{
				y = q.front().first;
				x = q.front().second;
				q.pop();
				for (int k = 0 ; k < 4 ; k++)
				{
					q_y = y + dy[k];
					q_x = x + dx[k];
					if (q_y < 0 || q_x < 0 || q_y >= N || q_x >= N || visited[q_y][q_x] || height[q_y][q_x] <= b_height)
					continue;
					visited[q_y][q_x] = 1;
					q.push({q_y, q_x});
				}
			}
		}
	}
	if (!cnt)
		return (0);
	ans = std::max(ans, cnt);
	return (1);
}

void solve()
{
	int i = 0;

	while (++i <= 100 && bfs(i))
		;
}

void print_val()
{
	std::cout << ans;
}

int main()
{
	input();
	solve();
	print_val();
	return (0);
}