백준 2589 : 보물섬

문제 링크 접근 방법 최장 최단 거리이므로 BFS 결과 중 가장 큰 값을 구한다. 삽질했던 부분 트리의 지름 처음 문제에 접근했을 때 효율적으로 풀기 위해서 임의의 한 점에 대해 가장 먼 지점을 구하고, 가장 먼 지점에서부터 BFS를 수행하여 먼 곳까지의 거리를 구하면 답이 나올 수 있다고 생각했다. 즉, 트리의 지름을 구하면 답이 될 것이라고 생각했다. 하지만 문제에 주어진 보물섬이 트리가 아닐 수 있기 때문에 오답이 나왔다. 처음에는 트리가 아닐 수 있다는 점이 이해가 되질 않았는데 luniro님의 반례를 통해 이해할 수 있었다. 반례 7 7 WLLLLLW LWLWLWW LLLWLWW LWWWLWW LLLLLWW LWWWWWW WWWWWWW 우선 문제 그대로 풀이하게 되면 그림 처럼 빨간색이 보물이 ..