백준 2468번 : 안전 영역 [C++]

 

 

 

 

 

 

DFS와 Brute Force를 사용하여 풀었다.

 

중요한 건, 

영역의 높이는 최소 1이므로 영역의 높이가 모두 0이고 수위도 0이여서 안전영역의 수가 0만 나오는 경우는 없다는 것!!

 

모든 영역이 같은 숫자일 경우엔 안전 영역의 수가 0아니면 1 이므로 최댓값은 1이된다는 것이다.

 

예를 들어, 모든 영역이 1이라면 수위가 0일 땐 전부 안잠기므로 안전영역은 1개가 되고,

수위가 1이상이 되면 모두 잠겨서 안전영역은 0개가 된다. 

 

즉, 1은 나올 수 있는 안전영역 수의 최솟값이 된다.

 

따라서, result의 초깃값은 1이다.

 

물의 높이가 따로 주어지지 않았기 때문에 입력을 받으면서 가장 낮은 영역과 가장 높은 영역을 따로 정의했다.

 

물높이는 입력 받은 영역의 높이에서 가장 낮은 높이 ~ 가장 높은 높이인 경우를 모두 살펴보는 반복문을 돌렸다.

 

 

 

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

const int MAX = 100;

typedef struct {
	int y, x;
}dir;

dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };


int N; 
int area[MAX][MAX];
int min_height, max_height;
bool visited[MAX][MAX];
int cnt, result = 1;

void DFS(int y, int x, int height) {
	visited[y][x] = true;
	
	for (int i = 0; i < 4; i++) {
		int nextY = y + moveDir[i].y;
		int nextX = x + moveDir[i].x;

		if (0 <= nextY && nextY < N && 0 <= nextX && nextX < N) {
			if (area[nextY][nextX] > height && !visited[nextY][nextX])
				DFS(nextY, nextX, height);
		}
	}
}



int main(void) {

	cin >> N;


	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> area[i][j];

			if (i == 0 && j == 0) {
				min_height = area[0][0];
				max_height = area[0][0];
			}
			else {
				min_height = min(min_height, area[i][j]);
				max_height = max(max_height, area[i][j]);
			}
		}
	}

	for (int k = min_height; k <= max_height; k++) {
		
		cnt = 0;
		memset(visited, false, sizeof(visited));

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (area[i][j] > k && !visited[i][j]) {
					DFS(i,j,k);
					cnt++;
				}
			}
		}

		result = max(result, cnt);
	}

	
	cout << result << endl;

	return 0;
}