[C++] 백준 2468: 안전 영역

문제

[C++] 백준 2468: 안전 영역 SILVER 1
https://www.acmicpc.net/problem/2468

 

---

 

접근 방법

비의 높이(rain)가 주어졌을 때, 잠기지 않은 영역(안전 영역)의 개수를 세고, 그 개수의 최댓값을 구하는 문제다.

핵심은 비의 높이가 바뀔 때마다 지도에서

• 높이 > rain 인 칸들만 “살아있는 땅”으로 보고
• 상하좌우로 연결된 덩어리(연결 요소)의 개수를 DFS/BFS로 세는 것이다.

그래서 rain을 0부터 (지도 최대 높이 - 1)까지 변화시키며 매번 탐색하고,
각 rain에 대한 안전 영역 개수 중 최댓값을 ret에 저장한다.

 

구현 시 주의할 점

• visited 초기화는 매 rain마다 반드시 해줘야 한다. (이전 rain 탐색 흔적이 남으면 오답)
• 탐색 조건은 vect[yy][xx] <= rain이면 잠긴 것이므로 continue 처리해야 한다.
• 마지막에 ret가 0인지 아닌지 판단하는 부분이 중요하다.
  비가 아예 오지 않는 경우(= rain = 0)에도 안전 영역은 최소 1개가 존재하는데,
  구현을 rain을 1부터만 돌리거나(혹은 전부 잠긴 케이스만 계산) 하면 ret이 0으로 남을 수 있다.
  그래서 최종 출력에서 ret == 0이면 1을 출력하도록 처리해주면 안정적으로 맞출 수 있다.
  이 부분 때문에 계속 실패가 떴었다...

 

---

 

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
vector<vector<int>> vect;
vector<vector<bool>> visited;

void bfs(int rain, int y, int x)
{
	queue<pair<int, int>> Q;
	Q.push(make_pair(y, x));
	visited[y][x] = true;

	while (!Q.empty())
	{
		int now[2] = { Q.front().first, Q.front().second };
		Q.pop();

		for (int i = 0; i < 4; i++)
		{
			int yy = now[0] + dy[i];
			int xx = now[1] + dx[i];

			if (yy < 0 || n <= yy || xx < 0 || n <= xx
				|| visited[yy][xx] == true || vect[yy][xx] <= rain)
				continue;

			visited[yy][xx] = true;
			Q.push(make_pair(yy, xx));
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	vect.resize(n, vector<int>(n, 0));

	int Max = 0, Min = 101;
	for (int y = 0; y < n; y++)
	{
		for (int x = 0; x < n; x++)
		{
			cin >> vect[y][x];

			if (Max < vect[y][x])
				Max = vect[y][x];
			if (Min > vect[y][x])
				Min = vect[y][x];
		}
	}
	int ret = 0;
	for (int i = Min; i <= Max; i++)
	{
		int cnt = 0;
		visited.resize(n, vector<bool>(n, false));
		for (int y = 0; y < n; y++)
		{
			for (int x = 0; x < n; x++)
			{
				if (vect[y][x] > i && visited[y][x] == false)
				{
					bfs(i, y, x);
					cnt++;
				}
			}
		}
		if (ret < cnt)
			ret = cnt;
		visited.clear();
	}
	if (ret == 0)
		cout << 1;
	else
		cout << ret;

	return 0;
}