[백준] 1167번 트리의 지름
트리의 지름이란, 트리의 노드 중에서 가장 먼 두 정점사의 거리 혹은 경로를 의미한다.
트리의 지름을 구하는 방법은 아래와 같다.
- 임의의 정점 x에서 가장 먼 정점 y를 찾는다
- 정점 y에서 가장 먼 정점 z를 찾는다
- 정점 y ~ 정점 z 사이의 거리를 구한다
이 문제의 핵심은 정점 y ~ 정점 z 가 트리의 지름이 되는 이유를 이해하는 것이다.
정점 y~ 정점z가 트리의 지름의 양 끝점이 된다는 말의 의미는, 임의의 한점에서 찾은 가장 먼 점은 항상 지름의 양 끝점 중 하나라는 뜻이다.
따라서 그 점에서 가장 멀리 있는 점은 트리의 양 끝점의 또 다른 한 점 이므로, 두 정점 사이의 거리가 트리의 지름이 되는것이다.
임의의 한점에서 가장 멀리 있는점은, 트리 지름의 양 끝점중 하나이다.
임의의 한 점에서 가장 멀리 있는 점은, 항상 트리 지름의 양끝점 중 한점이 될까?
정점 u와 정점v를 연결하는 경로가 트리의 지름이라고 하고, 임의의 정점x에서 가장 먼 정점은 y라고 할때,
이 정점들의 관계는 3가지로 표현될 수 있다.
- x가 u또는 v인 경우
- y가 u또는 v인 경우
- x,y 그리고 u,v가 모두 다른 정점인 경우
1,2의 경우를 생각해보자. x에서 가장 먼 점은 y이다.
만약 x가 u또는 v라면, x에서 가장 먼점은 트리의 지름중 나머지 한 점이 된다. 2번의 경우도 마찬가지이다.
문제는 3번의 경우이다.
3의 경우 두 가지 경우로 나누어서 생각할 수 있다.
a) x~y의 경로와 u~v 경로가 한 점이상을 공유하는 경우 (경로가 겹치는 경우)
d(a,b)를 a에서부터 b까지의 거리라고 하자.
정점 x에서 가장 먼 정점은 y이다. 이 말의 뜻은 점 t를 기준으로 x에서 가장 멀리 떨어져있는 점이 y라는 뜻이다
따라서 t~y까지의 거리가 u~t 또는 t~v까지의 거리 보다 크거나 같아야 , x에서 가장 먼 점이 y가 될 수 있다.
이를 수식으로 표현하면 d(t,y) >= max(d(u,t),d(t,v)) 이다.
-
d(t,y) > max(d(u,t),d(t,v)) 인 경우
정점 u에서 가장 먼점은 v이다. 이 말의 뜻은 점t가 갈 수 있는 경로중 가장 멀리 있는 점이 v라는 것인데 , 위의 가정에 따르면 t에서 가장 멀리 있는 점은 y가 되어야한다. 따라서 이 경우는 존재할 수 없다.
- d(t,y) = max(d(u,t),d(t,v)) 인 경우
이 가정이라면 정점x에서 가장 먼 정점은 y가 될 수 있고, 정점u에서 가장 먼 정점은 v가 될 수 있다.
∴ y는 u 또는 v 이다.
b) x~y의 경로와 u~v 경로가 독립적인 경우
이 그림에서 x~y와 u~v가 독립적인 경로라고 하였는데, 두 경로를 연결해놓은 이유는 트리의 특징 때문이다.
트리는 사이클이 없이 모든 노드가 연결된 그래프이다. 모든 정점은 루트 노드를 통해 연결된다.
따라서 트리의 어딘가에 이 두 경로가 만나는 공통 조상 노드가 반드시 존재하게된다.
정점 x에서 가장 먼 정점이 y라면, d5 >= d3+ max(d1,d2) 임을 알 수 있다.
또한 u에서 가장 먼 점이 v라는 것은 d2 >= d3+ max(d4,d5) 임을 알 수 있다.
그런데 이 두 식은 동시에 성립할 수 없다. 첫번째 식에 따르면 d5>d2 이고, 두번째 식에 따르면 d2>d5이다.
따라서 이 경우는 존재할 수 없다.
결론
(트리 구조에서) 임의의 한 점에서 가장 멀리 있는 점은, 항상 트리 지름의 양끝점 중 한점이다.
출처