시작

이 문제는 간단하게 푸는 문제는 아닌것 같다.필자는 변수 잘못 넘겨서 골머리 앓았음 우선 이 문제는 연결된 컴포넌트를 찾는 문제로, DFS즉 깊이 우선 탐색을 이용하여 해결하면 되는 문제! 우선 예외사항부터 알아보자

예외사항

1. 우선 범위를 넘어서면 안됨
2. 만약 방문했거나 그 칸이 침수칸이라면 넘기기

이런 예외사항이 있는데. 한번 감안하고 풀어보자면, BFS로 풀기엔 비효율적인 문제다. 그렇다면 왜 그런지 한번 알아보자. 우선 BFS는 본인 레벨의 노드들을 확인해야 되서 불필요한 부분까지 확인을 해야된다는 단점을 가지고 있으며 여기서 DFS는 자신의 밑 레벨의 노드를 바로 확인을 해서 이 문제에서는 사용을 하기에 좋은 알고리즘이다. 그렇다면 간단하게 알고리즘을 짜보자면

알고리즘

1. 모든칸을 한번씩 확인
2. 만약 그 칸이 방문을 했다면 넘기기
3. 만약 그 칸이 침수가 되었다면 넘기기

이런식으로 로직을 짠뒤에 계속 재귀함수를 돌려주면 되는 문제다. 밑은 문제를 한번 구현한 코드다.

코드

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<algorithm>
#include<cmath>
#include<tuple>

using namespace std;

int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
int N, minH = 9999, maxH = 0, counting = 0;
vector<vector<int>> _map;
vector<vector<int>> visited;
vector<int> maxBarigate(101, 0);

void DFS(int x, int y, int waterSize){
	if (visited[y][x] == 1 || _map[y][x] <= waterSize) return;
	visited[y][x] = 1;

	// 4방향 확인하기
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		// 범위 넘어가면 넘기기
		if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
		// 만약 방문했거나 침수된 칸이라면 넘기기
		if (visited[ny][nx] == 1 || _map[ny][nx] <= waterSize) continue;
		DFS(nx, ny, waterSize);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;

	_map.resize(N);
	visited.resize(N);
	for (int i = 0; i < N; i++) {
		_map[i].resize(N);
		visited[i].resize(N);
	}

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

	// 가장 높은 곳 -1 까지 침수 확인
	for (int i = 0; i <= maxH-1; i++) {
		// 방문 초기화
		for (int j = 0; j < N; j++) {
			fill(visited[j].begin(), visited[j].end(), 0);
		}
		counting = 0;
		// N^2으로 모든 칸 확인하기
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) {
				// 만약 방문한칸이거나 그 칸이 침수칸이라면 넘기기
				if (visited[j][k] == 1 || _map[j][k] <= i) continue;
				counting++;
				DFS(k, j, i);
			}
		}

		maxBarigate[i] = counting;
		
	}

	cout << *max_element(maxBarigate.begin(), maxBarigate.end());
}