[Algorithm] 트리의 지름

트리의 특징트리에서는 어떠한 두 정점을 고르더라도 두 정점 사이를 연결하는 경로는 유일하게 결정된다는 특징이 있습니다. 또한, 트리의 모든 정점은 트리의 root 역할을 수행할 수 있습니다. 각 간선에 가중치가 있는 트리 정보가 주어졌을 때, 트리의 지름이란모든 정점 쌍에 대한 거리 중 가장 긴 경로의 길이를 말합니다.트리의 지름을 찾는 알고리즘트리의 지름을 가장 쉽게 구하는 방법은 다음과 같습니다.아무 정점이나 잡고 시작해 DFS를 이용해 시작점으로부터 가장 먼 정점을 구합니다. 거리가 동일한 정점이 여러 개라면 아무 정점이나 골라도 상관없습니다. DFS를 통해 동일한 방식으로 위에서 구한 정점을 시작점으로 하였을 때, 가장 먼 정점을 구합니다.이때 구해진 거리가 트리의 지름이 됩니다.예로 아래 그림에..