1. 문제 설명

트리의 지름

2. 문제 분석

트리의 지름(이때 깊이가 아닌 비용의 최댓값)은 트리 내 특정 노드에서 최장 거리에 존재하는 노드를 구하고, 그 노드에서 다시 한 번 최장거리를 구해 글로벌 최장 거리를 구해야 한다.

• 루트 노드를 구한다 하더라도 지름이 깊이가 아니라 거쳐온 비용의 합계에 따라 결정된다는 데 주의.

3. 나의 풀이

import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
nodes = [[] for _ in range(n+1)]

for _ in range(n):
    edges = list(map(int, sys.stdin.readline().rstrip().split()))
    tail = edges[0]
    for i in range(1, len(edges)-2, 2):
        nodes[tail].append([edges[i], edges[i+1]])

def BFS(start):
    visited = [False for _ in range(n+1)]
    queue = deque()
    queue.append([start, 0])
    visited[start] = True
    max_cost, max_cost_node = 0, start

    while queue:
        cur_node, cur_cost = queue.popleft()

        if max_cost < cur_cost:
            max_cost = cur_cost
            max_cost_node = cur_node
            # 거쳐온 거리 중 최장 거리 및 노드 구한다.

        for next_node, next_cost in nodes[cur_node]:
            if not visited[next_node]:
                is_leaf = False
                visited[next_node] = True
                queue.append([next_node, cur_cost+next_cost])

    return max_cost_node, max_cost

node1, cost = BFS(1)
node2, cost = BFS(node1)
# 특정 노드의 최장 거리 노드에서 다시 최장 거리를 구한다.

print(cost)