[Python]트리 백준 1167

문제

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

트리의 지름을 구하라는 문제이다.

가장 먼저 생각할수 있는 건 모든 노드에서 BFS나 DFS를 통해 모든 길이를 구하면 그 

중 가장 긴 길이가 노드의 지름이 될것이다.

하지만 시간복잡도가 너무크다.

트리의 지름을 구하는 방법이 따로있다.

노드x에서 가장 먼 노드를 y라고 했을때 y는 지름을 이루는 노드중 하나이다.

증명은 이 블로그를 참고하면 이해하기 더욱 쉬울것이다.

https://blog.myungwoo.kr/112

이제 구현해보자.

임의의 노드x에 대해 DFS(x)에서의 최장거리를 이루는 y를 구하고 DFS(y)를 구해 최장

길이를 구하면 노드의 지름을 구할수 있다.

import sys
 
V=int(sys.stdin.readline())
 
matrix=[[] for _ in range(V+1)]
#입력받는 부분
for _ in range(V):
    path=list(map(int,sys.stdin.readline().split()))
    #1+2i
    path_len=len(path)
    for i in range(1,path_len//2):
        matrix[path[0]].append([path[2*i-1],path[2*i]])
 
 
#첫번째 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))