트리의지름

트리의지름 G4

문제

트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.

이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.

입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다.

트리의 노드는 1부터 n까지 번호가 매겨져 있다.

접근방법

트리는 무방향 그래프 이며, 두 노드 사이에는 항상 하나의 경로만 존재한다

트리의 지름 (Diameter of tree)

해당 블로그를 참고하여

1. 트리에서 아무노드 하나를 잡는다

2. 그 노드에서 가장 먼 노드를 구한다 ( n1 )

3. n1에서 가장 먼 노드를 하나 더 구한다 ( n2 )

4. n1 과 n2 가 트리의 지름이 된다

는 것을 활용하여 구현하였다

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def dfs(n, d):    
    global maxD

    left, right = 0, 0

    for node, w in arr[n]:
        r = dfs(node, w)
        if left <= right:
            left = max(left, r)
        else:
            right = max(right, r)

    maxD = max(maxD, left + right)
    return max(left + d, right + d)

n = int(input())
arr = [[] for _ in range(n + 1)]
maxD = 0

for _ in range(n - 1):
    a, b, c = map(int, input().split())

    arr[a].append([b, c])

dfs(1, 0)
print(maxD)