트리의 지름[파이썬 예제 코드]

트리의 지름을 구하는 방법은 간단하지만 이를 어떻게 증명하는지가 궁금하였다.

해당 포스트는 다음의 블로그 글을 제가 이해하기 편하게 정리한 내용입니다.

트리의 지름 구하기

제 글보다 훨씬 보기 쉽고 설명이 간단명료하게 잘 되어있기 때문에, 먼저 위의 블로그 포스트를 먼저 보시는 것을 추천 드립니다.

트리의 지름이란?

트리의 지름이란 트리에서 가장 먼 두 정점 사이의 거리를 의미한다.

트리의 지름 구하는 방법

트리의 지름을 구하는 방법은 다음과 같다.

• 트리에서 임의의 정점 x를 선택한다.
• 정점 x에서 가장 먼 정점 y를 찾는다.
• 정점 y에서 가장 먼 정점 z를 찾는다.

트리의 지름은 정점 y와 정점 z를 연결하는 경로다.

증명

앞서 소개한 트리의 지름 구하는 방법이 실제로 트리의 지름을 구할수 있다는 증명을 보이도록 하겠다.

트리의 지름을 구하는 방법을 머릿속에 기억하고 다음의 상황을 가정해보자.

트리에서 정점 u와 정점 v를 연결하는 경로가 트리의 지름이라고 가정을 하겠다.

임의의 정점 x를 정하고, 정점 x에서 가장 먼 정점 y를 찾았을 때, 다음과 같은 3가지 경우가 존재한다.

1. x가 u 혹은 v인 경우
2. y가 u 혹은 v인 경우
3. x, y, u, v가 서로 다른 경우

---

케이스1, 2에 대한 증명

1번에 대해서 알고리즘이 트리의 지름을 올바르게 구한다는 것을 증명해 보자.

다음과 같은 트리에서 $($u, t) = 4라면 $($y, t), $($t, v)의 값은 어떻게 될까?

$($y, t)를 6이라고 가정해보자. x에서 가장 거리가 먼 정점이 y이기 때문에 $($x, v) ≤ 10이어야 한다.

하지만 이와 동시에 $($u, v)가 트리의 지름이기 때문에 $($x, v)보다 작은 값을 가질수 없다.

따라서 $($y, t), $($t, v) 모두 같은 값을 갖게된다.

이때 완성된 트리에서의 지름은 $($y, v) = 12가 되는데 이는 곧 앞서 설명한 알고리즘이 트리의 지름을 올바르게 구한다는 것을 증명한다.

$($임의의 x에서 가장 먼 정점을 y라고 하였을때, 트리의 정점은 y에서 가장 먼 정점과의 연결하는 경로.)

위의 증명은 2.에도 적용되므로 이제 3. 경우에 대해서 증명하면 된다.

---

케이스3 에대한 증명

케이스3에는 아래와 같이 두 가지 경우가 가능하다.

1. 정점 x와 정점 y를 연결하는 경로가 정점 u와 정점 v를 연결하는 경로와 한 점 이상 공유하는 경우
2. 정점 x와 정점 y를 연결하는 경로가 정점 u와 정점 v를 연결하는 경로와 완전히 독립인 경우

다음과 같은 경우를 살펴보자.

x에서 가장 먼 정점이 y이기 때문에 $($t, y) ≥ $($t, v) or $($t, u) 이어야 한다.

이와 동시에 가정이 성립하도록 $($u, v)가 트리의 지름이 되어야 한다.

따라서 위의 예제의 경우, $($u, y) = 10 > $($u, v) = 9 로 $($u, v)가 트리의 지름이라는 가정을 위반하기 때문에 성립할 수 없다.

따라서 d$($t, y) = max$($ d$($t,u), d$($t,v) ) 이다.

$($u, v)가 트리의 지름이라고 가정하였기 때문에 $($x, t)는 4이하이다.

따라서 임의의 정점 x에서 가장 먼거리의 y를 찾고 y에서 가장 먼 지점이 트리의 지름이라는 공식이 증명된다.

---

두번째의 경우, 다음과 같은 상황이 되는데, u에서 제일 먼 지점이 v가 아니라 y가 되어 $($u, v)가 트리의 지름이 된다는 가정에 모순되므로 불가능하다는 것을 알 수 있다.

트리의 지름 구하는 방법 구현 $($Python)

트리의 지름 구하는 방법은 임의의 정점 x에서 깊이우선 탐색$($DFS)를 통해, 가장 먼 거리의 정점 y를 찾는다.

그 다음 y에서 다시 한번 깊이우선 탐색$($DFS)를 수행하여, 가장 먼 거리의 정점 z를 찾고 $($y, z)의 경로 값을 구하면, 이는 곧 트리의 지름이 된다.

# 정점의 개수 n
n = 10
# 임의의 정점 x로 부터 모든 노드들의 거리를 저장하기 위한 배열
firstDFS = [0 for _ in range(n + 1)]
# x에서 가장 먼 y정점으로 부터 모든 노드들의 거리를 저장하기 위한 배열
secondDFS = [0 for _ in range(n + 1)]
# 시작, 도착노드와 그 가중치를 저장하는 그래프
G = [[] for _ in range(n + 1)]
Max, idx = 0, 0

# 시작노드, 끝 노드, 가중치를 입력
for _ in range(n):
    path = list(map(int, input().split()))
    path_len = len(path)

    for i in range(1, path_len // 2):
        G[path[0]].append((path[2 * i - 1], path[2 * i]))

''' 트리의 지름 구하기 시작 '''
def DFS(start, G, result):
    for nextNode, cost in G[start]:
        # 방문한 적이 없으면 비용 갱신
        if result[nextNode] == 0:
            result[nextNode] = result[start] + cost
            DFS(nextNode, G, result)

# 임의의 정점 1로부터의 거리를 저장
DFS(1, G, firstDFS)
firstDFS[1] = 0

# 임의의 정점 x에서 가장 먼 거리의 y정점 까지의 경로 찾기
for i in range(len(firstDFS)):
    if Max < firstDFS[i]:
        Max = firstDFS[i]
        # y정점의 인덱스값 저장
        idx = i

DFS(idx, G, secondDFS)
secondDFS[idx] = 0

# 두번째 DFS에서 가장 먼 정점의 경로 출력
print(max(secondDFS))