백준 2468번: 안전 영역

https://www.acmicpc.net/problem/2468

---

간단한 BFS 문제였다.

물높이가 0에서부터 지역 중 최고 높은 지역의 높이까지 경우에서 안전 영역의 개수를 계산하여 가장 많은 안전 영역의 개수를 출력해주면 된다.

 

안전 영역의 개수는 물높이보다 높은 지역을 시작으로 인접한 칸에 물높이보다 높은 지역이 있는지 탐색하는 BFS를 수행하면서 방문체크를 하고, 모든 좌표를 탐색했을 때 수행한 BFS 탐색의 수가 곧 안전 영역의 개수가 된다.

---

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

int getMaxSafeAreaCount(const vector<vector<int>>& cityArr, int RainHeight)
{
	int N = cityArr.size();
	vector<vector<bool>> visited(N, vector<bool>(N, false));

	int safeAreaCount = 0;

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

	for(int y=0; y<N; y++)
		for (int x = 0; x < N; x++)
		{
			if (visited[y][x] || cityArr[y][x] <= RainHeight)
				continue;

			safeAreaCount++;

			queue<pair<int, int>> q;
			q.push({ y,x });
			visited[y][x] = true;

			while (!q.empty())
			{
				int hereY = q.front().first;
				int hereX = q.front().second;
				q.pop();

				for (int i = 0; i < 4; i++)
				{
					int nextY = hereY + dy[i];
					int nextX = hereX + dx[i];

					if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < N)
					{
						if (!visited[nextY][nextX] && cityArr[nextY][nextX] > RainHeight)
						{
							q.push({ nextY, nextX });
							visited[nextY][nextX] = true;
						}
					}
				}

			}
		}

	return safeAreaCount;
}

int main(void)
{
	int N;
	cin >> N;

	vector<vector<int>> cityArr(N, vector<int>(N));

	int maxHeight = 0;

	for(int y=0; y<N; y++)
		for (int x = 0; x < N; x++)
		{
			cin >> cityArr[y][x];
			maxHeight = max(maxHeight, cityArr[y][x]);
		}

	int maxSafeAreaCount = 0;

	for (int i = 0; i < maxHeight; i++)
	{
		maxSafeAreaCount = max(maxSafeAreaCount, getMaxSafeAreaCount(cityArr, i));
	}

	cout << maxSafeAreaCount;

	return 0;
}