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

문제

N x N 배열에 자연수가 입력될 때, 1 <= h <= N 에 대해 h를 초과하는 요소가 안전영역이라 하자. 인접한 안전영역끼리는 하나의 영역으로 칠 때, 안전한 영역의 최대 개수 출력

예제 입력 1

5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

예제 출력 1

5

예제 입력 2

7
9 9 9 9 9 9 9
9 2 1 2 1 2 9
9 1 8 7 8 1 9
9 2 7 9 7 2 9
9 1 8 7 8 1 9
9 2 1 2 1 2 9
9 9 9 9 9 9 9

예제 출력 2

6

알고리즘 분류

• 그래프 이론
• 브루트포스
• 그래프 탐색
• dfs
• bfs

---

풀이과정

dfs를 사용했다.

필요한 배열은 아래와 같다.

• 입력값을 할당할 2차원 배열 => arr
• 방문처리를 할 2차원 배열 => visited
• 각 높이에 대해 안전한 영역인지 확인하기 위한 2차원 배열 => map
• 인접한 영역 처리를 위한 배열 (y, x 각각)

선언해야 할 변수는 아래와 같다.

• 입력받은 값 중 가장 큰 수를 할당할 변수( maxH )
• 각 높이마다 영역의 개수를 계산할 변수( cnt )
• 최대 영역의 개수를 할당할 변수( maxCnt )
  
  
  

1. arr에 입력값 할당, maxH 할당

   for (int i = 0; i < N; i++)
   	for (int j = 0; j < N; j++)
   		cin >> arr[i][j];
   		maxH = max(arr[i][j], maxH);

2. 1부터 maxH까지 모두 돌려서 각각 안전영역의 개수를 구해야 하므로 for문 사용

• 해당 경우의 높이가 h라 하자.
  1. 각 경우마다 i, j에 대해 arr[i][j]가 h보다 작은지 확인해서 작다면 map[i][j]에 0을, 크다면 1을 할당한다.
  2. map[i][j] = 1이고 방문하지 않은 노드일 때 dfs함수를 호출하고, cnt값 증가
  3. 각 h에 대한 마지막 수행에서 visited를 초기화시키는 reset함수 호출

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;
int arr[101][101];
int map[101][101]; // 안잠기면 1
bool visited[101][101];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int cnt, maxCnt;
int N;
int maxH;
void dfs(int y, int x) {
		visited[y][x] = true;
		for (int i = 0; i < 4; i++) {
			int	yy = dy[i] + y;
			int xx = dx[i] + x;
			if (yy >= 0 && yy < N && xx >= 0 && xx < N) {
				if (map[yy][xx] && !visited[yy][xx]) dfs(yy, xx);
			}
		}
}

void reset() {
	maxCnt = max(cnt, maxCnt);
	cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			visited[i][j] = false;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
			maxH = max(arr[i][j], maxH);
		}
	}
	
	for (int h = 1; h <= maxH; h++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = arr[i][j] < h ? 0 : 1;
			}
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] && !visited[i][j]) {
					dfs(i, j);
					cnt++;
				}
			}
		}
		reset();
	}
	cout << maxCnt;
	return 0;
}