[백준, 2468번] 안전 영역 (DFS, 깊이 우선 탐색, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - 안전 영역" 문제는 다음과 다음과 같은 조건이있을 때 비의 양(즉, 높이)이 0부터 최대 높이까지 변할 때, 안전 영역의 최대 개수를 구하는 문제입니다.

 

• 어떤 지역의 높이가 주어졌을 때, 일정 높이 이하의 지역이 물에 잠긴다고 가정합니다.
• 이때, 물에 잠기지 않은 구역들을 "안전 영역"이라고 부릅니다.

즉, 물에 잠기지 않는 안전한 영역의 최대 개수를 출력하는 문제입니다.

 

---

이해를 돕기위해 예제 입력 1번을 가지고 접근해보겠습니다.

 

높이가 4일때는 왼쪽 그림과 같이 빨간색 영역이 물에 잠기게 되고, 높이가 5일 경우 오른쪽 그림과 같이 빨간색 영역이 물에 잠기게 됩니다.

 

그러면 물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽, 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다고 합니다.

 

물에 잠기지 않는 지점들을 구분해보면 다음과 같습니다.

 

위와 같이 높이가 4와 5일때 5개의 안전한 영역이 최대 개수로 나오게 됩니다.

---

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

 

높이는 문제에서 주어진 조건에 따라 1 이상 100 이하의 정수입니다.

 

하지만 우리는 안전 영역의 최대 개수만 구하면 되므로, 지역에서 최대 높이를 먼저 구합니다. 그 후, 높이가 1부터 최대 높이까지 반복하며, 각 높이에서 안전 영역의 개수를 계산합니다. 마지막으로 계산된 안전 영역 개수 중 최대값을 출력하면 됩니다.

이 때 아무 지역도 물에 잠기지 않을 수도 있기 때문에 높이가 0일 경우를 추가적으로 고려해야 할 수도 있습니다.

---

(0,0)에서 (N,N)까지 탐색을 하면서 안전 영역을 구해야 하기 때문에 모든 노드를 끝까지 탐색하는 깊이 우선 탐색(DFS) 알고리즘으로 효율적으로 풀 수 있습니다.

[Algorithm] 효율적인 그래프 탐색: 자바로 구현한 DFS 알아보기 (1/2)

---

전체 코드

 

문제의 핵심은 크게 3가지가 있습니다.

 

1. 높이에 따라 물에 잠기는 영역

 

• 각 높이(h)에서 지도 상에서 물에 잠기는 영역과 잠기지 않은 영역(안전 영역)을 구분해야 합니다.
• 물이 차오르는 높이를 0 ~ 최대 높이(maxH)까지 순차적으로 설정하며 시뮬레이션합니다.

 

2. DFS/BFS를 이용한 연결 요소 탐색

 

• 물에 잠기지 않은 영역이 서로 연결되어 있는지를 판단하기 위해 DFS(혹은 BFS)를 사용합니다.
• 하나의 연결된 영역을 탐색 완료하면 해당 영역을 하나의 안전 영역으로 간주합니다.
• 모든 지점에 대해 탐색을 반복하며, 방문 여부를 기록하는 visited 배열을 사용해 중복 탐색을 방지합니다.

 

3. 안전 영역의 최대값 계산

 

• 각 높이(h)에서 탐색한 안전 영역의 개수를 기록하고, 모든 높이에 대해 최대값을 업데이트 하면서 최대 개수의 안전영역을 구해나갑니다.
• 즉, 높이에 따라 물에 잠기지 않는 최대 안전 영역을 찾는 것이 목표입니다.

---

 

주의 사항❗️

각 높이마다 새로운 안전영역을 찾아야 하기 때문에 각 높이마다 visited 배열을 초기화 해줘야 합니다.

 

visited 배열을 초기화하지 않으면, 높이 1에서 방문한 지역이 높이 2,3,4...에서도 계속 방문한 것으로 표시되어 있게 됩니다.

예시:

• 높이 1에서 (0,0) 방문 → visited[0][0] = true
• 높이 2에서 (0,0) 검사 → 이미 visited[0][0] = true라서 건너뜀
• 결과적으로 새로운 높이에서의 안전영역을 제대로 계산할 수 없음

따라서 각 높이마다 새롭게 방문 여부를 체크해야 합니다.