[백준 알고리즘(BOJ)] 2468번 안전영역 문제 자바(java) 풀이

BOJ 2468번 안전영역 문제 자바(java) 풀이

• 랭크 : 실버2
• 백준 온라인 저지(BOJ) 2468번 안전영역 문제 자바 풀이
• 백준 2468번 안전영역
  
  
  

문제정리

1. 지역 마다 높이 정보가 주어진다.
2. 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇개가 만들어 지는지 조사한다.
3. 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다.
4. 지역의 높이는 2차원 배열의 형태로 주어진다.
5. 안전영역 : 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역
6. 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전 영역의 개수가 다르다

• 지역의 높이들이 주어졌을때, 물에 잠기지 않는 안전한 영역의 최대 개수를 계산해라!!
  
  
  

문제풀이

이 문제는 전형적인 dfs 문제라고 볼 수 있습니다.
0. 입력을 받고 지역의 최대 높이도 동시에 구합니다.

1. 내리는 비의 양이 0,1,... max 일때 각각 안전영역의 개수를 구합니다.
   • 비의 양에 따라 그보다 작은 수를 가지는 지역은 0으로 만듭니다.
   • 그리고 dfs를 돌며 0이 아닌 지역을 탐색합니다.(방문하지 않은 곳에서 만 시작)
   • dfs 를 돌게되면 그때마다 하나의 영역을 탐색하는 것이므로 count를 증가시킵니다.
2. 비의 양에 따라 각각 안전영역의 개수를 구해서 최대값을 update합니다.
   
   
   

dfs

첫 번째 안전영역

이 문제는 dfs로 탐색만 하면 영역의 개수를 구할 수 있습니다.
예를 들어 다음과 같은 map으로 설명드리겠습니다.

<잠기기 전>
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

여기서 비의 양이 4라면 4보다 작은 지역은 물에 잠겨서 0이 됩니다.
<잠긴후>
6 8 0 6 0
0 0 0 0 6
6 7 0 0 0
7 0 5 0 6
8 9 5 0 7

이제 0,0 지점 부터 탐색을 시작합니다. 이때 방문하지 않았으면서 0이 아닌 점을 탐색합니다.
<visited 상태>
t t f f f
f f f f f
f f f f f
f f f f f
f f f f f
시작점인 6을 방문하고 다음 방문 할 수 있는 곳이 8밖에 없으므로 8을 방문합니다.
그 다음에 사방이 0이고 왼쪽은 방문했으므로 방문할 곳이 없어서 dfs를 탈출하게 됩니다.
이렇게 안전 영역 하나를 구하였습니다.

두 번째 안전영역

그 다음 방문하지 않았고 0이 아닌 곳은 0,3번째 입니다. (행 기준 탐색)

t t f t f
f f f f f
f f f f f
f f f f f
f f f f f
그러면 visited는 위와 같이 변하고, 사방으로 0이기 때문에 더 갈 수 있는 곳이 없어서 dfs 함수를 탈충하고 2번째 안전영역을 구할 수 있습니다.

세 번째 안전영역

다음으로 방문할 수 있는 곳은 (0,4) 위치 입니다.

t t f t f
f f f f t
f f f f f
f f f f f
f f f f f
방문하고 나면 위와 visited는 위와 같이 변하고 이도 2번째 안전영역을 구할때와 같은 상황이 되서 탈출하고 3번째 안전영역을 구할 수 있습니다.

네 번째 안전영역

다음 방문할 수 있는 곳은 (2,0) 위치 입니다.

t t f t f
f f f f t
t t f f f
t f t f f
t t t f f

(2,0) -> (3,0) -> (4,0) -> (4,1) -> (4,2) -> (3,2) -> (2,1)
이렇게 총 7군데를 방문할 수 있습니다. 이렇게 4번째 영역을 구하였습니다.

다섯 번째 안전영역

3번째 줄은 이제 모두 방문하였기에 갈 수 있는 곳이 없고 4번째 줄로 이동해서
(3,4)를 방문할 수 있습니다.

t t f t f
f f f f t
t t f f f
t f t f t
t t t f t

(3,4)와 (4,4)를 방문하고 5번째 영역을 구하였습니다.
이제 방문하지 않았으면서 0인 곳은 없으므로 dfs 함수에 들어가지 않고 for문을 빠져나오게 됩니다.
이렇게 비의 양이 4일때 총 5개의 영역을 구하였습니다.