[백준 2468] 안전 영역 (Java)

문제

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

2468번: 안전 영역

 

풀이

 

설계의 방향성은 상.하.좌.우 재귀적 탐색을 바탕으로 한 그래프탐색이였다. 

Worst Case의 경우 배열이 100 X 100 크기지만, 모든영역을 탐색하는 것이 아닌 적절한 Pruning 과정이 있을 것이라 생각하여 가능할 것이라 판단하였다.

 

첫번째 시도(틀림): 안전한영역이 아닌 침수된 영역을 탐색하였다. 그러다보니, "안전한 영역"의 최대개수가 아닌 "침수된 영역"의 최대개수가 나왔다. -> 문제의 목표를 정확히 파악하자.

 

 

 

두번째 시도: 

우리의 목표는 각 강수량별 물에 잠기지 않는 안전한 영역의 최대개수를 구하는 것이다.

 

 

1. 강수량의 범위는 어떻게 잡아야할까?

배열의 최저높이인 강수량부터 침수가 시작되고, 최고높이인 강수량일 경우 모두 침수가 될 것이니

강수량: 최저높이 ~ 최고높이 일 경우를 조사하면 될 것이다.

for (int rain=minHeight; rain<=maxHeight; rain++) {
   ...
   dfs탐색
   ...
}

 

 

2. 탐색시작은 어떻게 설정해야할까?

우리의 탐색목표는 "안전한 영역"의 개수를 파악하는 것이고 우린 탐색을 시작하면 재귀적 탐색으로 같은 영역에 대하여 계속해서 탐색을 진행할 것이다. 따라서, "최초" 탐색시작은 영역개수 + 1임을 의미한다. (이 후 재귀적 탐색은 같은 영역이므로 영역개수 증가가 아님.)

이 논리에 의해, 우린 이미 방문한 영역은 다시 방문할 필요가 없으며, 침수된 영역또한 방문할 필요가 없다.

 

int count = 0;
for (int i=0; i<N; i++) {
	for (int j=0; j<N; j++) {
	//탐색시작
 		if(!visit[i][j] && board[i][j] > rain) {
			count ++;
			visit[i][j] = true;
			dfs(i, j, rain);
		}
	}
}

 

3. 재귀적 탐색은 어떻게 진행될까?

위의 그림을 보면 이해가 될 것이다. 

1. 배열의 범위 안에서만 재귀적 탐색이 가능하고,

2. 우리의 목표는 안전한영역 탐색이기 때문에 강수량보다 높은 지점만 탐색이 가능하고,

3. 재귀의 스택오버플로우를 방지하기 위해 방문안한 곳만 탐색한다.

 

private static void dfs(int x, int y, int rain) {
		
	for (int i=0; i<4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
			
		//배열범위 검출
		if(nx>=0 && nx<N && ny>=0 && ny<N) {
			//안전한영역이고, 방문안한 지점만 재귀적 방문
			if(board[nx][ny]>rain && !visit[nx][ny]) {
				visit[nx][ny] = true;
				dfs(nx, ny, rain);
			}
		}
	}
}

 

 

최종 코드

public class Main {
	static int[] dx = {1, -1, 0 , 0};
	static int[] dy = {0, 0, 1, -1};
	static int[][] board;
	static boolean[][] visit;
	static int N;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		board = new int[N][N];
		visit = new boolean[N][N];
		int minHeight = 0;
		int maxHeight = 0;
		
		
		for (int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j=0; j<N; j++) {
				int height = Integer.parseInt(st.nextToken());
				board[i][j] = height;
				minHeight = Math.min(minHeight, height);
				maxHeight = Math.max(maxHeight, height);
			}
		}
		//maxSave: 안전영역 최대개수
		int maxSave = 1;
		//조사할 강수량 범위
		for (int rain=minHeight; rain<=maxHeight; rain++) {
			
			//count: 안전영역 count
			int count = 0;
			//visit 배열 초기화
			arrayFill();
			
			for (int i=0; i<N; i++) {
				for (int j=0; j<N; j++) {
					//탐색시작
					if(!visit[i][j] && board[i][j] > rain) {
						count ++;
						visit[i][j] = true;
						dfs(i, j, rain);
					}
				}
			}
			maxSave = Math.max(maxSave, count);
		}
		System.out.println(maxSave);
		
		
	}

	private static void dfs(int x, int y, int rain) {
		
		for (int i=0; i<4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			//배열범위 검출
			if(nx>=0 && nx<N && ny>=0 && ny<N) {
				
				//안전한영역이고, 방문안한 지점만 재귀적 방문
				if(board[nx][ny]>rain && !visit[nx][ny]) {
					visit[nx][ny] = true;
					dfs(nx, ny, rain);
				}
			}
		}
		
	}
	private static void arrayFill() {
		for (int i=0; i<visit.length; i++) {
			Arrays.fill(visit[i], false);
		}
		
	}
}

 

※주의:

1. Edge Case

최초 maxSave (안전한 영역의 최대개수)는 0이 아니라, 1이다.

아무지점도 침수되지 않았다면 영역개수는 0이 아니라, 1이므로.

 

2. visit배열 초기화

특정 강수량에 대한 조사가 끝났다면, visit배열을 초기화해주는 작업이 필요하다.

 

 

 

결과

 

 

 

요약

상.하.좌.우 재귀적 탐색문제

1. 탐색 시작위치 고려

2. 어떤식으로 Pruning하여 재귀적탐색을 수행할 것인지 설계