2468 안전영역

최근 풀이 : 240528

-> 풀었음!

최근 풀이 : 240312

height 를 1부터 시작하면 69퍼센트에서 틀림
https://www.acmicpc.net/submit/2468/74824158

height 를 0부터 시작하면 100퍼센트 맞음.
https://www.acmicpc.net/submit/2468/74824189

• 왜냐하면, 문제의 마지막 노트에 아무지역도 물에 잠기지 않을수 있다고 한다.
  가 있기 때문인데.
  건물의 높이라고 했을 때 높이는 1이상 100이하 이기 때문에
  아무지역도 잠기지 않는 0을 셋팅하고 진행해야하기 때문이다.

vector.clear 를 할 경우,

중요!
원소가 지워지는 것뿐 아니라, 그냥 사이즈 자체가 0이되어 버림...

---

언제 풀어봄.

: 220908 09:34 ~ 10:16

문제를 잘읽어보자.

: 비의 양이 얼만큼의 범위를 가지고 동작한다는 말은 없음.

참고 사이트
https://www.acmicpc.net/board/view/96703

• 입력 높이는 2 ~ 100 인데,
  비가 1이하로 발생한다면 ? 안전영역은 1임.

처음에는 final을 0으로 설정했음.
하지만, 위의 설명대로 비가 1 이하로 발생한다면?
-> 안전영역은 1임. 즉 최소값은 1부터 시작해야함...

코드

#include <iostream>
using namespace std;
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>

int n;

// 상하좌우 
int dx[]{ 0,0,-1,1 };
int dy[]{ -1,1,0,0 };

bool dfs(vector<vector<int>>&v , vector<vector<bool>>&check, 
	int height , int sero , int garo)
{
	// 테두리 안에서만 돌아야 함.
	if ((0 > sero || sero >= n)
		 || (0 > garo || garo >= n))
	{
		return false;
	}
	
	if (check[sero][garo] == true)
	{
		return false;
	}

	// 높이 검증
	if (v[sero][garo] > height)
	{
		check[sero][garo] = true;
	}
	// 중요함. 높이 이하인 친구들을 처리해야 함.
	else
		return false;

	for (int i = 0; i < 4; ++i)
	{

		//if (check[sero][garo] )
		//int nx = garo + dx[i];
		//int ny = sero + dy[i];

		
		{
			dfs(v, check, height, sero + dy[i], garo + dx[i]);
		}
		
	}

	//cout << "1" << endl;
	return true;
}


int main()
{
	// n 이하인 지점은 모두 잠김? 
	// -> n 보다 큰 지점들을 dfs로 돌림.
	// n + 1 인곳의 상하좌우를 탐색하면 됨. 

	// n = 4 -> 5이상인 곳을 탐색함. 

	
	cin >> n;

	vector<vector<int>>v(n, vector<int>(n));

	int mmin = 101;
	int mmax = 0;

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			cin >> v[i][j];
		}
		mmax = max(mmax, *max_element(v[i].begin(), v[i].end()));
		mmin = min(mmin, *min_element(v[i].begin(), v[i].end()));
	}

	//cout << mmax << " " << mmin << endl;
	// min ~ max 높이를 선정하자. 

	int ffinal = 1;
	
	for (int k = mmin; k < mmax; ++k)
	{
		vector<vector<bool>>check(n, vector<bool>(n, false));
		int res = 0;
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if (check[i][j] == false)
				{

					if (dfs(v, check, k, i, j))
					{
						//cout << "2" << endl;

						++res;
					}
				}
			}
		}

		ffinal = max(ffinal, res);
	}
	cout << ffinal;

}