Algorithm: 트리 지름

트리의 지름이란 트리의 두 정점 u 와 v 를 잇는 거리의 최대값이다. 즉, 트리 내에서 가장 먼 두 정점 사이의 거리를 의미한다.

트리

트리의 지름

 

Brute-Force Method

모든 가능한 u, v 의 조합을 다 해본다

이 때 걸리는 시간은 O(n^3)

--> 비효율적

 

O(n) 알고리즘

• 트리에서 임의의 정점 x를 선택한다
• x에서 가장 먼 정점 y를 BFS 를 통해 찾는다
• y 에서 가장 먼 정점 z를 찾는다
• y 와 z 가 가장 멀리 떨어져 있는 정점이다.
• 위 방법의 증명은 다음과 같다
  • 원하는 답이 u 와 v 라고 하자. 이때, x를 정한 뒤 가장 먼 점이 y라고 한다면 3가지 가능성이 존재한다
    • x = u (or v)
    • y = u (or v)
    • x,y,u,v 는 모두 다른 경우
  • x = u (or v) 나 y = u(or v) 의 경우 답이 맞다는 것이 자명하다. 하지만 x,y,u,v 가 모두 다른 경우는 오직 한가지인데, 이는 최대 거리가  동일한 경우이다. ex) u ~ y == u ~ v
  • x,y,u,v가 모두 다를 때, 만약 x ~ y의 경로와 u ~ v 의 경로가 교점 t를 가지는 경우(가질수도 있고 아닐수도 있음)
    • y 가 x 에서 가장 먼 정점이 아니려면 --> t~y가 t~ v 보다 멀어야 한다. 
      • 그러지 않을 경우, y 가 x에서 가장 먼 노드라는 가정이 어긋난다.
      • 즉, u~t~y 가 u~t~v 보다 멀다.
      •  

• 교점 t 가 없을 경우
  • x~y 와 u~v 를 잇는 경로가 존재해야 하는데 이를 a~b 라고 하겠다
  • 정의상, a~y의 거리가 a~b~u, a~b~v 보다 멀다(y 가 x에서 가장 먼 점이기 때문.
  • u ~ v 의 거리와 u ~ y 의 거리를 비교해 보자.
    • 이때, u ~ b 는 둘 모두 포함.
    • 즉, b~a~y 와 b~v를 비교.
    • a~ y 가 a~b~v 보다 멀다
      • 즉 b~a~y 가 더 멀고, u~v의 거리가 u~y 보다 짧다.