[백준 2468] 안전 영역

문제
NxN의 맵에 각 칸에는 지역의 높이 정보가 담겨져있다. 장마철에 많은 비가 내려 높이가 4이하인 모든 지점에 물이 잠긴다고 하면 물에 잠기지 않은 지역 중 인접한 영역들을 안전영역이라 한다.
인접한 영역은 상하좌우를 기준으로 한다.
이때 이 지역에서 물에 잠기지 않는 안전한 영역의 최대 개수를 구하라.

입력
첫째 줄에 지역의 크기를 나타내는 N이 주어진다. 
(2이상 100이하)
이후 맵에 대한 정보가 입력되며 각각의 높이는 1이상 100이하이다.

출력
장마철에 물에 잠기지 않는 안전영역의 최대 개수를 출력한다.

---

접근

비의 양을 조절하면서 안전영역을 구해 최댓값을 비교해야 한다. 비의 양은 0부터 입력받은 높이 중 최대 높임만큼 온다고 설정한다. 그리고 이 범위 안에서 FOR문을 돌아 안전영역을 구한다.

해당 맵으로 여러번 DFS를 진행해야하기 때문에 원본 맵을 복사한다. 복사할 때는 비의 양보다 작거나 같은 지역은0, 비의 양보다 높은 지역은 1로 표시한다. 이후 2차원 배열을 탐색할 때 1을 만났을 때 DFS를 진행하고 DFS를 진행한 횟수가 안전영역의 개수가 된다.

 

구현

먼저 맵에 대한 정보를 입력받는다.

동시에 최대 높이를 구하여 max_height에 저장한다. 그리고 비의 양을 0부터 max_height으로 설정한다.

	int max_height = 0;
	
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			max_height = max(max_height, map[i][j]);
		}
	}

 

원본 맵에서 h이하인 지역은 0으로 복사하고 그렇지 않으면 1로 복사한다.

최종적으로 copy_map에는 잠긴지역은 0, 아닌지역은 1로 표시된다.

for (int h = 0; h <= max_height; h++) {
		// 안전영역 크기 
		int count = 0;
		
		//원본 맵 -> 복사 맵 (강수량 h이하는 -1)
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] <= h)
					copy_map[i][j] = 0;
				else
					copy_map[i][j] = 1;
			}
		}

 

복사된 맵을 활용해서 1일 때 DFS를 진행하고 안전영역의 개수(count)를 증가시킨다.

		// 복사맵으로 dfs 진행
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (copy_map[i][j] ==1) {
					++count;
					DFS(i, j);
				}
			}
		}

 

DFS에서는 전달받은 인자의 위치에 0을 대입하여 방문표시를 한다.

이후 상하좌우 중 범위를 벗어나지 않고 1인 지역에대해 DFS를 또 실행한다.

void DFS(int y, int x) {
	copy_map[y][x] = 0;

	for (int d = 0; d < 4; d++) {
		int ny = y + dir[d][0];
		int nx = x + dir[d][1];
		if (RangeCheck(ny, nx) && copy_map[ny][nx]==1) {
			DFS(ny, nx);
		}
	}
}

 

위의 과정을 거치면 안전영역의 개수가 나오고 이를 비교하여 최대 안전영역의 수를 구하도록한다.

---

전체 코드

#include <iostream>
#include<algorithm>
#include <vector>
#include<queue>
#include<cstring>

using namespace std;

const int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };

int N;
int map[100][100];
int copy_map[100][100];

bool RangeCheck(int y, int x) {
	return(y >= 0 && y < N) && (x >= 0 && x < N);
}

void DFS(int y, int x) {
	copy_map[y][x] = 0;

	for (int d = 0; d < 4; d++) {
		int ny = y + dir[d][0];
		int nx = x + dir[d][1];
		if (RangeCheck(ny, nx) && copy_map[ny][nx]==1) {
			DFS(ny, nx);
		}
	}
}
int main()
{
	int max_height = 0;
	
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			max_height = max(max_height, map[i][j]);
		}
	}

	int answer = 0;
	
	for (int h = 0; h <= max_height; h++) {
		// 안전영역 크기 
		int count = 0;
		
		//원본 맵 -> 복사 맵 (강수량 h이하는 -1)
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] <= h)
					copy_map[i][j] = 0;
				else
					copy_map[i][j] = 1;
			}
		}

		// 복사맵으로 dfs 진행
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (copy_map[i][j] ==1) {
					++count;
					DFS(i, j);
				}
			}
		}

		
		answer = max(answer, count);

	}
	
	cout << answer << endl;
	return 0;
}

/*
강수량은 1~100
1부터 강수량을 조절해보면서 안전영역 구하기
매번 강수량이 변할 때 방문표시를 초기화해줘야함

안전영역을 구하는 것은 DFS로 방문표시 맵에 TRUE로 표시

매 반복마다
원본 맵에서 H이하는 -1로 이외는 그대로 복사하기 => 복사맵도 전역변수
복사맵으로 2차원 탐색 진행하여 0초과일 때 DFS 진행 -> DFS 진행횟수가 안전영역의 개수
DFS 안에서는 전달받은 인자의 위치에 -1을 대입하여 방문표시

이후 DFS횟수로 최댓값 비교

*/

---