[Python] 트리의 지름을 구하는 법

결론부터 말하면 트리의 지름은 임의의 한 점에서 가장 멀리 떨어져 있는 점(A)과, 해당 점(A)에서 부터 가장 멀리 떨어진 점(B) 사이의 거리(AB)이다.

 

즉, 한 점(n)으로 부터 DFS(n)으로 가장 먼 점(A)을 구하고, 해당 점(A)에서 DFS(A)로 가장 먼 점(B)과의 거리가 된다.

 

이제부터 이 이유에 대해서 생각해보자.

 

트리의 특징 중 사이클이 존재하지 않는다. 즉, 지나간 노드는 다시 방문할 수 없다. 이것을 기억하자.

 

트리는 어떤 점을 기준으로 잡아도 트리가 된다. 예를 들어보자.

 

[예시1]

 

위와 같은 트리가 있다고 가정해보자.

 

만약 3번 노드를 잡고 위로 올려서 다른 노드들이 데롱데롱 매달리게 된다고 생각해보면 아래와 같은 그림이 된다.

[예시2]

 

어느 노드를 잡고 아래로 내리게 되든지 트리와 같은 모양이 된다. 

 

"여기서 트리의 지름을 어떻게 구할까?"

 

간단히 생각해서 [예시2]를 봤을 때 노드 3을 기준으로 오른쪽(노드 6) 방향으로 가장 긴 선분과, 왼쪽(노드 1) 방향으로 가장 긴 선분의 두 길이를 더해주면 된다.

 

따라서 노드 3에서 가장 먼 노드를 찾아준다. 그러면 노드 4와 노드 5가 될 것이다. 그리고 해당 두 점, 노드 4와 노드 5에서 다시 가장 먼 노드를 찾아주면 6번을 찾을 것이다. 따라서 노드 4와 노드 6, 또는 노드 5와 노드 6을 잇는 길이가 트리의 지름이 될 것이다.

 

예시1에서도 똑같이 적용될 것이다.

 

[예시1]

1에서 가장 먼 점은 노드 4, 노드 5, 노드 6이 될 것이다. 해당 점에서 가장 먼 점을 다시 찾으면 노드 6, 노드 6, 노드 4(또는 노드 5)가 나올 것이다. 따라서 위의 방법은 어떤 경우에서든 트리의 최장 지름을 구할 수 있다.