백준 - 2468번 : 안전 영역 (C++)

풀이 방법 : 브루트 포스 , 깊이우선 탐색

각 높이로 물이 잠겼을때 생길 수 있는 안전 영역의 수를 모두 카운트 해주면 된다. 그래서 set 컨테이너에 각 지역의 높이 정보들을 넣어놓고 중복없이 해당 높이에 대해서 모든 경우를 탐색해주었다.

#include <iostream>
#include <memory.h>
#include <set>

using namespace std;

int Vilage[101][101] = {};
bool Check[101][101] = {};
int DirY[4] = { 1,-1,0,0 };
int DirX[4] = { 0,0,1,-1 };

int Max = 1;

void DFS(int N, int MaxHeight);
void DFS(int CurY, int CurX, int N, int MaxHeight);

void DFS(int N, int MaxHeight)
{
	int Cnt = 0;

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			if (Check[i][j] || Vilage[i][j] <= MaxHeight)
				continue;

			++Cnt;

			Check[i][j] = true;
			DFS(i, j, N, MaxHeight);
		}
	}

	Max = max(Cnt, Max);
}

void DFS(int CurY, int CurX, int N, int MaxHeight)
{
	for (int i = 0; i < 4; ++i)
	{
		int NextY = CurY + DirY[i];
		int NextX = CurX + DirX[i];

		bool IsOutOfBounds = NextY < 0 || NextY >= N || NextX < 0 || NextX >= N;

		if (IsOutOfBounds)
			continue;

		if (Check[NextY][NextX])
			continue;

		Check[NextY][NextX] = true;

		if (Vilage[NextY][NextX] <= MaxHeight)
			continue;

		DFS(NextY, NextX, N, MaxHeight);
	}
}

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	set<int> setHeight;

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cin >> Vilage[i][j];
			setHeight.insert(Vilage[i][j]);
		}
	}

	auto iter = setHeight.begin();
	auto iterEnd = setHeight.end();

	for (; iter != iterEnd; ++iter)
	{
		DFS(N, *iter);

		memset(Check, 0, 101 * 101);
	}


	cout << Max;
}