[JAVA] 안전 영역 ::: BFS

[ 문제 ]

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

 

 

 

[ 제출코드 ]

 

 

 

[ 풀이 ]

물의 높이가 0일 때부터 땅의 최대 높이일 때까지 반복하면서 BFS로 안전 영역을 탐색합니다.

각 물의 높이에서의 안전 영역 중 최대값을 정답으로 출력합니다.

 

 

 

[ 이야기 ]

BFS로 구현한 코드가 예제 테스트는 성공하는데 제출만하면 계속 실패했습니다...

반례들도 넣어가면서 했지만 실패를 했는데 아래 참고 블로그를 보고 while의 조건문을 잘못 주었다는 것을 알게 되었습니다.

물의 높이가 0일 때부터 계속 반복하면서 안전 영역의 개수가 줄어드는 시점이 되면 그 전의 개수가 가장 최댓값인 줄 알았는데 아니었습니다. 그래서 while의 조건은 물의 높이가 0일 때부터 땅의 최대 높이까지 반복시키는 것으로 수정하니 통과할 수 있었습니다.

 

 

 

[ 참고 ]

https://replay2.tistory.com/entry/%EB%B0%B1%EC%A4%80-2468-%EC%95%88%EC%A0%84%EC%98%81%EC%97%AD-bfs-java