트리의 지름 - 백준 1967번

https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

 

 

DFS를 사용해 트리를 추적하는 문제이다.

먼저 말단 노드까지 도착한 뒤 올라오면서 왼쪽 오른쪽 자식 노드들의 길이와 합을 구한다.

트리의 지름은 무조건 왼쪽 최장경로 + 오른쪽 최장경로 이다.

 

DFS로 리프 노드까지 내려간 뒤 해당 노드의 가중치를 리턴한다.그리고 자식 노드가 있는 부모 노드부터는 자식들의 경로들 중 가장 큰 두 길이를 선택한다.두 길이를 더한 것은 현재 노드를 기준으로 지름이 된다.어느 기준 노드의 지름이 가장 클 지 알 수 없으니 지름을 전역 변수로 하나 생성해두고 더 큰 지름이 나올 때마다 갱신해준다.상위 부모 노드로 갱신해줄 때에는 왼쪽과 오른쪽 경로 중 더 큰 것을 리턴해준다.

 

import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)

N=int(input())
tree=defaultdict(list)
maxDist=0
for _ in range(N-1):
    root,child,weight=map(int,sys.stdin.readline().split())
    tree[root].append([child,weight])

def dfs(node,weight):
    left,right=0,0
    for child,w in tree[node]:
        r=dfs(child,w)
        if left<=right:
            left=max(left,r)
        else:
            right=max(right,r)
            
    global maxDist
    maxDist=max(maxDist,left+right)
    return max(left+weight,right+weight)

dfs(1,0)
print(maxDist)