[bfs/백준] 1967번 : 트리의 지름

- 문제 : https://www.acmicpc.net/problem/1967

 

잎노드에서 시작을 해야할 것 같은데, 잎 노드에서 가장 먼 잎 노드를 어떻게 찾지?하며 어떻게 풀어야할지 몰랐던 문제다 

 

풀이 방법은 

일단 루트 노드에서 가장 먼 잎 노드를 구한다. 

그 잎노드에서 가장 멀리 있는 잎노드를 구한다

거기까지의 가중치 합을 출력하면 된다 

 

- 정답 풀이 : 

import sys
sys.setrecursionlimit(10**6)

n=int(input())
data=[[] for _ in range(n+1)]

for _ in range(n-1):
    a,b,c=map(int,input().split())
    data[a].append([b,c])
    data[b].append([a,c])
    
def dfs(x,weight):
    for i in data[x]:
        a,b=i
        if distance[a]==-1:
            #a노드 방문처리 
            distance[a]=b+weight
            dfs(a,b+weight)
distance=[-1]*(n+1)
distance[1]=0
dfs(1,0)

#루트노드로부터 가장 멀리 있는 잎 노드 번호 구하기 
start=distance.index(max(distance))
distance=[-1]*(n+1)
#해당 잎 노드를 루트노드로 가장 먼 잎 노드를 찾는다 
distance[start]=0
dfs(start,0)
            
print(max(distance))