[BOJ] 백준 2468번 - 안전 영역(with Java)

알고리즘

문제를 읽어보면 DFS를 사용하여 연결 요소의 개수를 알아내는 [BOJ] 4963번 - 섬의 개수 문제와 비슷하다고 느껴질 수도 있다. 이 문제의 최대 변수는 '강수량'이다. 문제에서는 '비의 양에 따라서 생기는 안전영역의 최대 개수'를 구하라고 하는데, 입력에는 비의 양이 주어지지 않고 노트에는 잘 와닿지 않는 힌트가 적혀있어서 문제를 완벽하게 이해하지 못한 상태에서 풀게 되었다. 

우선 DFS 메소드의 경우에는 '섬의 개수' 문제에서 사용한 방식을 그대로 적용하되, 8방향에서 4방향으로 바꿔주고 'arr[nr][nc]=1'이 아닌 'arr[nr][nc]>height'로 바꿔줘야 빗물의 높이보다 영역의 높이가 높아져서 안전 영역이 생성된다.

 

이제 메인 메소드를 보자. 빗물의 높이 정보는 나와있지 않지만, 영역의 높이가 최소 1부터 최대 100까지라고 주어졌으므로 빗물의 높이도 이와 똑같이 생각할 수 있다. 빗물의 높이가 영역의 높이보다 높거나 같은 경우에는 안전영역의 개수는 무조건 0이 나오므로 불필요한 계산을 줄이기 위해서 최대 높이를 추출해주었다. 빗물의 높이에 따라서 모든 경우를 각각 테스트해봐야하므로 브루트-포스 알고리즘이 적용되었음을 알 수 있다.

 

이어서 빗물의 높이에 따른 안전영역의 개수를 구하기 위해서 ArrayList를 생성 및 0을 추가하여 초기화를 진행하였다. 그리고 빗물의 높이에 따라서 반복문을 수행한다. 이때 주의할 점은 아까 빗물의 높이는 최소 1부터 최대 100까지라고 말했지만, 비가 오지 않는 상황도 있을 수 있으므로 height의 초기값을 0으로 잡아줘야 한다는 점이다. 문제에서는 이에 관한 정보가 두루뭉술하게 나와있기 때문에 풀이에 상당한 시간이 걸렸는데, 독자분들은 이 점을 알고 풀이를 해봤으면 한다. 이후에는 [BOJ] 4963번 - 섬의 개수 문제와 동일한 방식으로 모든 영역들에 대해서 DFS를 수행해주면 된다.

 

소스코드

문제링크

2468번: 안전 영역