Baekjoon Online Judge 1967번 파이썬

문제 링크
https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

for node, d in tree[start]: 로 자식 노드를 방문하므로 visited 배열을 사용할 필요가 없다.

어떤 노드의 자식 노드가 여러개 일 때, 각각의 방향으로 나아간 거리가 가장 먼, 두개의 길이를 이용하였다.

정답 코드

import sys
sys.setrecursionlimit(10 ** 6)

n = int(sys.stdin.readline())

tree = [[]for i in range(n+1)]
for i in range(n-1):
  input = list(map(int,sys.stdin.readline().split()))
  tree[input[0]].append((input[1],input[2]))
  

def dfs(start):
  global result
  left, right = 0, 0 
  for node,d in tree[start]:
    distance = dfs(node) + d # distance = left + d.
    if distance > left:
      left,right = distance, left #계속해서 비교해나가기 위해 더 긴 것을 left, 더 짧은 것을 right
    elif distance > right:
      right = distance
    result = max(result, left + right)

  return left #더 긴 길이는 left이기 때문에 left이기 때문에 distance = dfs(node) + d에 left가 이용되어야 한다.
  
distance = 0  
result = 0
dfs(1)
print(result)