[백준] 실버1-안전 영역 C++ 2468번

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

 

// 반례 - [최소,최대/없거나,있거나] 생각하기

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

int N;
int adj[100][100];
int cnt = 1;	// 아무 구역도 잠기지 않을 경우 1개임
bool visited[100][100];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };

void clearArr()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			visited[i][j] = 0;
		}
	}
}

void dfs(int y, int x, int depth)
{
	visited[y][x] = 1;

	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
		if (adj[ny][nx] <= depth) continue;
		if (visited[ny][nx]) continue;

		dfs(ny, nx, depth);
	}
}

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

	cin >> N;
	int maxH = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> adj[i][j];
			if (maxH < adj[i][j])
				maxH = adj[i][j];
		}
	}

	for (int d = 1; d <= maxH; d++)
	{
		int maxCnt = 0;
		clearArr();
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (adj[i][j] > d && !visited[i][j])
				{
					maxCnt++;
					dfs(i, j, d);
				}
			}
		}
		if (maxCnt > cnt)
			cnt = maxCnt;
	}
	cout << cnt;
	

	return 0;
}