[ baekjoon ] 트리의 지름 1967번 ( python )

문제

백준 1967 트리의 지름 풀이 ( 파이썬 )

www.acmicpc.net/problem/1967

1967번: 트리의 지름

 

 

풀이

한 노드를 정하고 가장 깊은 노드를 탐색한 후 그 노드에서 다시 가장 깊은 노드를 탐색했다.

import sys
sys.setrecursionlimit(10**9)

input=sys.stdin.readline

n=int(input())

result1=[0 for _ in range(n+1)]
result2=[0 for _ in range(n+1)]
tree=[[] for _ in range(n+1)]

def dfs(cur,result):
    for i in range(len(tree[cur])):
        end,dis=tree[cur][i]
        if result[end] == 0:
            result[end]=result[cur]+dis
            dfs(end,result)

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

dfs(1,result1)
result1[1]=0
maxi=0
index=0

for i in range(len(result1)):
    if maxi<result1[i]:
        maxi=result1[i]
        index=i

dfs(index,result2)
result2[index]=0

print(max(result2))