[C/C++] 코드업(codeup) 4697번 안전 영역

▽문제 바로가기

https://codeup.kr/problem.php?id=4697

안전 영역

---

입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다.

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

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

높이는 1이상 100 이하의 정수이다.

 

출력

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

 

문제 풀이

 

각 지역의 높이는 1 이상 100 이하입니다. 잠기는 범위를 0부터 100까지 구현해도 되지만 입력받을 때 가장 큰 값을 저장해서 그 값까지 탐색하면 시간을 절약할 수 있습니다.

 

평소에 하던대로 구현했을 때 한 가지 문제점이 있었습니다.

예를 들어 5이하인5 이하인 지역이 물에 잠긴다고 했을 때 6 이상의 지역에 대해서 인접한 지역을 탐색한다고 했을 때 탐색한 지역을 5 이하인 값으로 바꾸어야 재탐색을 안 합니다.

문제는 이렇게 하면 5 이하인 지역에 대한 탐색이 끝나고 6 이하인 지역에 대한 탐색이 시작될 때 이미 맵은 흩트려진 상태입니다.

따라서 맵을 입력받을 때 temp배열에 저장했다가 탐색이 끝나면 바로 복구하는 식으로 구현하여 해결했습니다.

 

#include <stdio.h>

using namespace std;

int n;
int arr[101][101] = {0,};
int temp[101][101] = {0,};	//맵 복구를 위한 배열
int dy[4] = {0, 0, 1, -1};	//동서남북탐색
int dx[4] = {1, -1, 0, 0}; 

void dfs(int row, int col, int d){
	//범위 밖이면 리턴
	if(row==-1||col==-1||row==n||col==n) return;
	
	//잠기는 영역이면 리턴
	if(arr[row][col]<=d) return;
	
	//색칠안되어있다면 탐색
	arr[row][col] = d;	//중복 탐색 방지
	for(int i=0;i<4;i++){
		dfs(row+dy[i], col+dx[i], d);
	}
}

int main(){
	 
	scanf("%d", &n);
	int loop = 0;	//입력받는 값중 가장 큰 값을 저장
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			scanf("%d", &arr[i][j]);
			temp[i][j] = arr[i][j];
			if(loop<arr[i][j]) loop = arr[i][j];
		}
	}
	
	int max = 0;
	//물 잠기는 영역이 0부터 가장 큰 값까지 탐색
	for(int k=0;k<=loop;k++){
		int x = 0;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				//물에 안잠기는 안전 영역이면
				if(arr[i][j]>k){
					dfs(i, j, k);
					x++;
				}
				arr[i][j] = temp[i][j];	//맵 복구
			}	
		}
		//영역의 최대 개수교환
		if(max<x) max = x;
	}
	
	printf("%d", max);
	
	return 0;
}