[백준 1967] 트리의 지름

[ 백준 1967 : 트리의 지름 ]

이런 모양의 트리가 있을때 두 개의 점을 양 손으로 잡고 펴본다고 생각하자.
이때 각 간선마다 값이 있는데 이 값의 합이 가장 클 때의 합을 출력하면 된다.

예제의 테스트 케이스는 이렇게 두개의 점을 잡으면 된다고 한다.

처음 문제를 접했을때 LCA라고 생각했다. 총 노드의 갯수가 1000이라고 봤고
1초에 들어오게 풀 수 있다고 생각했다.

그래서 (1,2) (1,3) (1,4) ....(5,6) (5,7) (5,8)....(N-1 , N) 이런식으로
모든 두개의 점을 다 선택하고 그중 최댓값을 찾았는데.. 시간초과가 나왔다.


어떻게 접근할까? 일단 임의의 어떤 한 점에서 DFS를 이용해
가장 긴 거리를 가진 노드A를 찾는다.
그리고 그 노드에서 또 다시 DFS를 이용해 가장 긴 다른 노드B를 찾으면된다.
그러면 A와 B의 거리가 가장 긴 거리임을 알 수 있다.

왜?
임의의 어떤 한 점C를 보면 C에서 가장 먼 거리를 가진 노드 A를 볼 수 있다.
그럼 이 C와 A 사이에 있는 간선들 집합 중에는
무조건 가장 길이가 긴 간선들이 포함되어있을 것이다.
시간은 N-1만큼이 걸릴것이다.

그리고 A점을 기준으로 다시 또 DFS로 전체를 다 본다.
이때 계속 더 탐색하며 현재의 최대값보다 커질때마다 갱신을 해주면 최대값이 나온다.
그리고 이 최대값은 A를 기준으로 가장 긴 노드 B와의 거리가 될 것이다.