백준 2589 - 보물섬

백준 2589 - 보물섬

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

풀이

문제를 보고 BFS 알고리즘을 활용해야겠다는 생각을 했다.

하지만, 육지 중에서 가장 멀리 있는 땅 두 곳의 최단 거리를 구하는 문제이기 때문에, 한번의 BFS로는 답을 구하기 어렵겠다는 생각을 하게 되었다.

따라서 지도 중 L인 각 칸마다 BFS를 실행하여 가장 긴 거리를 찾아야겠다고 생각했다.

시간 제한이 1초임을 확인하고, 지도의 크기가 각각 50이하이므로, 50 × 50의 지도의 각 칸에 대해 모두 BFS를 실행하는 최악의 경우를 상정해도 시간제한에 걸리지 않는다고 판단하였다.

처음 문제를 풀었을 때, 시작점의 거리를 0으로 두고 풀어서 오답이 나왔다.

이는 처음 0으로 둔 거리에서 퍼져나갔을 때, 다시 시작점을 검사하면 시작점으로 BFS를 재 진행하는 문제가 있음을 알게 되었고, 시작점을 1부터 시작하여 정답에서 -1을 해주는 방식으로 해결하였다.

코드