[Baekjoon]2468.안전 영역

2468.안전 영역

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

---

연구소, 단지번호 붙이기 등 탐색 문제와 비슷한 방법으로 풀 수 있는 문제였다. 

1. 강수량 1증가.
2. 탐색으로 안전영역 카운트.
3. 최댓값이면 갱신, 아니면 1로 돌아가서 반복.

탐색은 dfs를 이용했고 explore메소드는 맵을 순회하며 dfs를 할지 말지 결정하는 메소드이다. 단지 번호 붙이기에서도 같은 방법을 사용했다. 다른 문제풀이와 다른 점은 flood메소드에 있다.

 

먼저 모든 지역이 물에 잠길 때까지만 함수를 실행하기위해 주어진 맵의 최고점을 max에 저장해놓고 while문을 통해 강수량이 max보다 작을 동안에만 실행했다. 또한 강수량이 증가할때마다 탐색을 다시 진행하기위해 visited배열을 초기화했다. 

private static void flood() {
		while (pptn < max) {
			cnt = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] <= pptn) {
						map[i][j] = 0; // 침수된 곳은 0
					}
				}
			}
			for (boolean row[] : visited) {
				Arrays.fill(row, false);
			}
			explore();
			ans = Math.max(ans, cnt);
			pptn++;
		}
		return;
	}

<전체코드>