BaekJoon 1967번 : 트리의 지름 (python)

BaekJoon 1967번 : 트리의 지름 (G4 40.726%)

트리의 지름 문제

이전의 트리의 지름문제와 같은 BFS or DFS를 두 번 반복하는 문제이다.

• 이번 문제에서는 문제에서 주어진 루트 노드 1번을 통해 1번 노드에서부터 가장 멀리 떨어진 트리의 끝점을 찾아준다.
• 해당 노드에서 BFS 한 번 더 돌아주며 가장 먼 노드들, 즉 트리의 가장 끝점에 있는 노드들과거의 거리를 비교해가며 가장 멀리 떨어져 있는 노드와의 길이를 찾을 수 있게 된다.

import sys
from collections import deque
input = sys.stdin.readline

def bfs(start) :
    q = deque()
    q.append((start,0))
    distance = [-1]*(n+1)
    distance[start] = 0
    temp = (0,0)
    while q :
        x, current = q.popleft()
        for i, dis in node[x] :
            if distance[i] == -1 :
                distance[i] = current + dis
                q.append((i,distance[i]))
                if distance[i] > temp[1] :
                    temp = (i, distance[i])

    return temp
n = int(input())
node = [[] for _ in range(n+1)]
for _ in range(n-1) :
    a,b,c = map(int,input().split())
    node[a].append((b,c))
    node[b].append((a,c))
temp = bfs(1)
result = bfs(temp[0])
print(result[1])