트리에서 아무 노드나 하나 잡고(루트 노드) dfs로 가장 멀리 있는 노드를 찾는다. 그리고 찾은 노드에서 가장 멀리 떨어져 있는 노드까지의 거리가 트리의 지름이다.
왜 이렇게 되는걸까? 맨 처음에는 루트에서 멀리 있는 노드 두 개 찾아서 더하면 정답인 줄 알았다. 그런데 맨 처음 잡은 노드(루트 노드)를 지나지 않으면서 지름이 되는 경우도 존재한다. 간단한 그림으로 해당 case에 대해 알아보자.
그림 한 장으로 깔끔하게 정리가 되었다.
그렇다면 루트 노드도, 루트에서 가장 멀리 떨어진 노드도 지나지 않는 경우는 없는걸까? 이 경우도 그림을 통해 알아보자.
2번 경로가 우리가 찾는 경로고, 3번 경로가 루트 노드, 루트 노드와 가장 멀리 떨어진 노드 둘 다 지나지 않는 경로다. 부등식을 세워서 조금만 계산해 보면, 3번 경로는 2번 경로보다 길 수 없다는 사실을 알 수 있다.
import sys
input = sys.stdin.readline
n = int(input())
tree = [[] for _ in range(n+1)]
dist = [0] * (n+1)
visited = [False] * (n+1)
for _ in range(n):
input_list = list(map(int, input().split()))
p = input_list[0]
for i in range(1, len(input_list) - 1, 2):
if i < 0:
break
tree[p].append((input_list[i], input_list[i+1]))
def dfs(n, v):
for i in tree[n]:
if not visited[i[0]]:
visited[i[0]] = True
d = dfs(i[0], v+i[1])
dist[i[0]] = d
return v
visited[1] = True
dfs(1, 0)
m = 0
idx = 0
for i in range(1, n+1):
if dist[i] > m:
m = dist[i]
idx = i
visited = [False] * (n+1)
dist = [0] * (n+1)
visited[idx] = True
dfs(idx, 0)
print(max(dist))
이런걸 그냥 바로바로 생각해내는 사람들은 머리가 얼마 나 좋은거지? 난 금붕어다.