[BOJ/C++] 안전 영역(2468번)

1. 문제 개요

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

2468번: 안전 영역

1-1. 설명

장마철에 대비해 재난방재청에는 다음일을 계획중이다. 어떤 지역 높이 정보를 파악한 후, 그 지역에 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇개까지 만들어지는지 조사한다. 아래의 예시를 보자 

행과 열의 크기가 각각 5인 2차원 배열 형태로 지역이 주어지며, 각 숫자는 지역 높이 정보이다. 이제 위와 같은 지역에 비가 내려 4이하인 모든 지점이 물에 잠겼다고 가정하자. 그럼 아래의 그림처럼 잠긴 부분은 회색으로 표시될 것이다.

물에 잠기지 않는 안전한 영역은 흰색 부분이며, 위의 경우에는 물에 잠기지 않는 안전한 영역은 5개가 된다. 또한 높이가 6이하인 지점을 모두 잠기게 만드는 비가 내리면 아래 그림처럼 안전한 영역은 네 개가 됨을 확인할 수 있다. 

이와 같이 장마철에 내리는 비의 양에 따라 물에 잠기지 않는 안전한 영역 개수는 다르다. 

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성해보자

1-2. 제한 사항

 - 첫줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 N 입력

 - N은 2이상 100이하의 정수 

 - 둘째 줄부터 N개의 각줄에는 2차원 배열의 첫번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보 입력

 - 각 줄에는 각 행의 첫번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈칸을 사이에 두고 입력

 - 높이는 1 이상 100 이하의 정수

---

2. 구현

2-1. 풀이

안전한 영역을 탐색해보자고 생각하여 DFS로 구현하였다. 우선 각 지역의 입력을 받을때 최대 높이를 구한 후, 1부터 최대 높이로 for문을 돌려 물에 잠기지 않는 안전 영역을 계산하기로 한다. 1부터 최대 높이의 물의 양을 계산할 때, 방문한 노드를 boolean 배열로 두어 반복할 때마다 초기화를 진행한다. 

2-2. 코드 

#include <iostream>

using namespace std;

void DFS(int x, int y, int h);
void initVisited();

int matrix[100][100];
bool visited[100][100];
int dirX[4] = { -1, 1, 0, 0 }; // x 방향 지정
int dirY[4] = { 0, 0, -1, 1 }; // y 방향 지정
bool check = false;
int N;

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

	int result, maxNum;

	cin >> N;
	maxNum = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> matrix[i][j]; // 지역 저장
			if (maxNum < matrix[i][j]) maxNum = matrix[i][j];
		}
	}

	result = 1;
	for (int height = 1; height <= maxNum; height++) {
		int currentArea = 0; // 현재 물 높이의 안전 영역 개수
		initVisited(); // 방문한 노드 초기화
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (matrix[i][j] > height && !visited[i][j]) { // 방문하지 않고 잠긴 영역보다 높을 시
					DFS(i, j, height);
					currentArea += 1;
				}

			}
		}
		if (currentArea > result) result = currentArea;
	}
	cout << result << "\n";
}

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

void DFS(int x, int y, int h) {
	if (!visited[x][y]) visited[x][y] = true; // 방문함을 알림
	for (int i = 0; i < 4; i++) {
		int nextX = x + dirX[i]; // 다음 노드의 X 방향
		int nextY = y + dirY[i]; // 다음 노드의 Y 방향
		if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N) { // 지역을 벗어나지 않을 때
			if (matrix[nextX][nextY] > h && !visited[nextX][nextY]) DFS(nextX, nextY, h);
			// 안전 지역이고 방문하지 않았을 때 DFS 호출
		}
	}