백준 2468 : 안전 영역

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

1. 접근

• 이 문제도 문제가 꽤 길지만, 결국 물의 높이를 기준으로 연결요소를 구하면 되는 문제이다.
• 대신 물의 높이가 고정이 아니고, 직접 모든 물의 높이를 확인해주어야한다.
• 배열의 크기와 높이의 범위가 작기때문에 1초 안에 실행될 수 있으므로 이 경우에는 완전탐색을 해주었다. 그게 아니라면 이분탐색을 고민해봤어야할지도 모르겠다..
• DFS로 한번씩 연결요소들을 체크해주고 그 때마다 ret값을 증가시켜 영역의 개수를 구했다.

2. 나의 풀이

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int n;
bool visited[101][101];
int map[101][101];

int dr[4] = { 0,0,-1,1 };
int dc[4] = { -1,1,0,0 };


void DFS(int startC, int startR, int num) {
	visited[startC][startR] = true;

	for (int i = 0; i < 4; i++) {
		int nc = startC + dc[i];
		int nr = startR + dr[i];

		if (nc >= 0 && nc < n&&nr >= 0 && nr < n && !visited[nc][nr]) {
			if (map[nc][nr] > num)	DFS(nc, nr, num);
		}
	}
}

int findArea(int num) {
	int ret = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] > num && !visited[i][j]) {
				ret++;
				DFS(i, j,num);
			}
		}
	}
	//cout << "높이 " << num << "일때 ret : " << ret << "\n";
	return ret;
}

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

	cin >> n;

	int minheight = -1;
	int maxheight = -1;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (minheight == -1|| minheight > map[i][j])	minheight = map[i][j];
			if (maxheight == -1 || maxheight < map[i][j])	maxheight = map[i][j];
		}
	}

	int ret = 1;
	for (int i = minheight; i <= maxheight; i++) {
		memset(visited, false, sizeof(visited));
		ret=max(ret,findArea(i));
	}
	
	cout << ret << "\n";

	return 0;
}