BFS, 트리 - 1167번: 트리의 지름

1) 트리에서 임의의 정점 s에서 가장 먼 정점 a를 찾기
2) 이 a는 지름 경로의 한 끝점!
3) 다시 a에서 BFS를 돌려 가장 먼 정점과 그 거리를 구하기 -> 이때의 가장 먼 거리가 트리의 지름
-> BFS 2번으로 O(N)에 해결 가능함!

from collections import defaultdict, deque
import sys

input = sys.stdin.readline

v = int(input())
graph = defaultdict(list)
leaf_nodes = []


for i in range(v):
    line = list(map(int, input().split()))
    idx = line[0]
    j = 1
    while line[j] != -1:
        graph[idx].append((line[j], line[j + 1]))
        j += 2
    if j == 3:
        leaf_nodes.append(idx)


def bfs(start):
    q = deque()
    visited = [False] * (v + 1)

    q.append((start, 0))
    visited[start] = True  # 시작점 방문처리 잊지 말기!

    max_dist = -1
    max_node = 0

    while q:
        node, dist = q.popleft()

        if dist > max_dist:
            max_dist = dist
            max_node = node

        child = graph[node]

        for c, e in child:
            if not visited[c]:
                visited[c] = True
                q.append((c, dist + e))

    return max_dist, max_node


dist, node = bfs(1)
dist, node = bfs(node)
print(dist)