[자료구조] 트리의 지름

가중치가 있는 간선으로 연결된 트리에서 지름을 알아보자. 이를 통해 트리의 특징들을 더 깊게 이해할 수 있을 것이다. 트리의 지름을 알아보기 위해 백준 1967 트리의 지름 문제를 참고하였다.

---

트리의 지름이란

트리는 N개의 노드로 이루어졌을 때 N-1개의 간선으로 연결되기 때문에 순환되지 않는 구조를 갖고있다. 따라서 노드 A에서 노드 B로 이동하는 경로를 하나밖에 없다. 이때 두 개의 노드를 양쪽으로 잡아당겼을 때 가장 길게 늘어나는 경우가 생기며 특정 원 안에 트리가 들어온다. 여기서 생긴 원의 지름을 트리의 지름이라고 한다.

 

트리의 지름 구하기

그렇다면 트리의 간선들에 가중치가 있을 때 트리의 지름을 어떻게 구할 수 있을까? 아래의 트리를 보면 트리의 지름을 구성하는 두 개의 노드는 9번 노드와 12번 노드이며 두 개의 노드 모두 리프 노드이다. 

트리의 지름을 구성하는 노드들은 리프 노드라는 것을 알 수 있다. 만약 4번 노드에서 출발하여 다른 리프 노드까지의 거리를 구해보면 트리의 지름이 될 수 없는 것을 확인할 수 있다. 그렇다면 트리의 지름을 구성하는 두 개의 리프 노드는 어떻게 구할 수 있을까?

 

위의 트리를 보면 특정 노드에서 출발하여 다른 노드까지의 거리가 가장 먼 노드를 찾아봤을 때 9번 노드 또는 12번 노드가 나오게 된다. 즉 임의의 노드를 기준으로 가장 먼 노드를 찾았다면 이 노드는 트리의 지름을 구성하는 노드 중 하나가 된다.

 

이제 위에서 구한 노드를 기준으로 가장 먼 노드를 찾는다면 해당 길이가 트리의 지름이 될 것이다.

 

구현하기

트리의 지름 구하는 것을 Python으로 구현해보자.

• N-1개의 간선 정보를 입력받아 가중치와 함께 저장한다.

for _ in range(N-1):
    a, b, w = map(int, input().split())
    tree[a].append([b, w])
    tree[b].append([a, w])

 

• 이제 BFS를 통해 특정 node를 루트 노드로 하여 가장 먼 노드를 찾아 그 때의 거리와 함께 반환한다.
• 루트 노드를 기준으로 가장 가까운 노드부터 방문하면서 가중치와 이전까지 노드의 거리를 더해서 자식 노드의 거리에 저장한다.
• 연결된 자식 노드가 -1이라면 아직 방문하지 않은 것이다.
• 탐색 중에 최댓값 비교를 하여 가장 먼 노드와 거리를 찾은 후에 반환한다.

def bfs(node):
    q = deque()
    dist = [-1] * (N + 1)
    dist[node] = 0
    q.append(node)
    result = [0, 0]

    while q:
        parent = q.popleft()

        for child, weight in tree[parent]:
            if dist[child] == -1:
                dist[child] = dist[parent] + weight
                q.append(child)
                if dist[child] > result[1]:
                    result = [child, dist[child]]
    return result

 

 

• 아래의 코드는 모든 노드를 루트 노드로 했을 때 가장 먼 노드를 찾아 출력한 것이다.
• 결과를 확인해보면 트리의 지름을 구성하는 두 개의 노드 중 하나의 노드가 나오는 것을 알 수 있다.

for start in range(1, N+1):
    far_node, dist = bfs(start)
    print(start, '-', far_node, ':', dist)
    node, dist = bfs(far_node)

---

정리

• 트리의 지름을 구성하는 노드들은 리프 노드가 된다.
• 트리의 지름을 구하기 위해 임의의 노드를 기준으로 가장 먼 노드를 찾고 이 노드에서 가장 먼 노드를 찾는다.
• 위의 방법으로 해결할 수 있다는 것을 증명할 필요가 있다.