BOJ 1967 트리의 지름

https://www.acmicpc.net/problem/1967
시간 2초, 메모리 128MB
input :

• n(1 ≤ n ≤ 10,000)
• a b c (a = 부모 노드의 번호 / b = 자식 노드 / c = 간선의 가중치)
• 부모 노드의 번호가 작은 것이 먼저 입력되고,
• 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼저 입력된다.
• 루트 노드의 번호는 항상 1이라고 가정
• 간선의 가중치는 100보다 크지 않은 양의 정수

output :

• 트리의 지름을 출력

---

아까 보았던 트리의 지름 문제와 동일한데...
인접 리스트를 저장할 때 양방향으로 저장해 주어야
맨처음 가장 먼 임의의 정점b를 구하고,

정점 b에서 부터 BFS를 수행해서
정점 c를 구할 수 있다.

import sys
from _collections import deque

n = int(sys.stdin.readline())
graph = [[] for i in range(n + 1)]


for i in range(n - 1):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((b, c))
    graph[b].append((a, c))


def bfs(start):
    q = deque()
    q.append((start, 0))
    visit[start] = 1
    ret = -9999

    while q:
        now, dis = q.popleft()
        for link in graph[now]:
            next_node, next_dis = link[0], link[1]
            if not visit[next_node]:
                visit[next_node] = 1
                q.append((next_node, dis + next_dis))
        if dis > ret:
            ret = dis
            node = now
    return ret, node


rad = -9999
visit = [0] * (n + 1)
dis, b = bfs(1)

visit = [0] * (n + 1)
dis, c = bfs(b)

print(dis)