[DFS] 1967. 트리의 지름 (Python)

문제

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

풀이

1. 한 노드 기준에서 각 정점까지 거리를 구하기
2. 가장 먼 길이에 해당하는 노드 찾기
3. 2번의 노드를 기준으로 거리 구하는 과정을 한번 더 반복하면 됨

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

def dfs(idx,v):
    for n_idx, n_val in tree[idx]:
        if visited[n_idx] == -1:
            visited[n_idx] = v+n_val
            dfs(n_idx,v+n_val)

n = int(input())
tree = {}
for i in range(1,n+1):
    tree[i] = []
for _ in range(n-1):
    a,b,c = map(int, input().split())
    tree[a].append([b,c])
    tree[b].append([a,c])


visited = [-1]*(n+1)
visited[1] =0
dfs(1,0)
last_node = visited.index(max(visited))
visited = [-1] * (n + 1)
visited[last_node] = 0
dfs(last_node,0)
print(max(visited))