[BOJ]2589번: 보물섬

 

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

---

문제 해결의 핵심은 그래프 크기가 작다는 것입니다.

W, H제한이 50이므로

모든 칸에 대해 새롭게 BFS를 돌아도 시간복잡도는 O(50^4) 이므로 시간초과가 나지 않습니다.

 

W*H칸에 존재하는 모든 육지에 대해 BFS를 돌아서 자신이 가장 멀리 도달한 지점을 저장해놓습니다.

이렇게 멀리 도달한 지점들의 MAX값을 구하면 그게 정답입니다. 

---

https://github.com/cottory/algorithm/blob/master/BOJ/BOJ2589.cc