[Python]트리 백준 1967

문제

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

이전 문제와 동일하다.

루트노드가 정해져 있지만 중요하지않다.

꼭 루트노드를 지나는 것은 아니기 때문에 앞문제와 마찬가지로 임의의 노드에서 DFS를 

통해 최장길이를 이루는 노드를 구한뒤

그노드에서 다시 DFS를 통해 가장 긴 길이를 구하면 트리의 지름이 된다.

이번문제는 sys.setrecursionlimit(10**9)를 통해 재귀 최대 깊이를 설정해 주지 않으면

 런타임 에러가난다.

import sys
sys.setrecursionlimit(10**9)
 
V=int(sys.stdin.readline())
 
matrix=[[] for _ in range(V+1)]
#입력받는 부분
for _ in range(V-1):
    s,e,d=map(int,sys.stdin.readline().split())
    matrix[s].append([e,d])
    matrix[e].append([s,d])
 
 
#첫번째 DFS결과
result1=[0 for _ in range(V+1)]
 
def DFS(start,matrix,result):
    for e,d in matrix[start]:
        if result[e]==0:
            result[e]=result[start]+d
            DFS(e,matrix,result)
 
DFS(1,matrix,result1)#아무노드에서 시작해준다.
result1[1]=0#루트노드가 정해져 있지않아 양방향으로 입력을 받기때문에 해당
 
 
tmpmax=0#최대값 구하기
index=0#최장경로 노드
 
for i in range(len(result1)):
    if tmpmax<result1[i]:
        tmpmax=result1[i]
        index=i
 
#최장경로 노드에서 다시 DFS를 통해 트리지름구하기
result2=[0 for _ in range(V+1)]
DFS(index,matrix,result2)
result2[index]=0
print(max(result2))