문제

풀이

트리와 bfs로 풀었다.

트리의 지름 구하기

1. 트리의 지름 : 가장 먼 두 노드 사이의 거리
2. 선형 시간 안에 트리의 지름을 구하는 방법
   1) 트리에서 임의의 노드 x를 설정
   2) 노드 x를 기준으로 가장 먼 노드 y를 탐색한다.
   3) 노드 y를 기준으로 가장 먼 노드 z를 탐색한다.
   4) 트리의 지름 : 노드 y와 노드 z 사이의 거리

참고
https://blog.myungwoo.kr/112

코드

# 1167 트리의 지름

from collections import deque
import random

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

for _ in range(n):
  node = list(map(int, input().split()))
  # 맨 왼쪽 정점번호와 -1은 필요없어서 -2, 정수 두 개씩 주어지니 step = 2

  for i in range(1, len(node) - 2, 2):
    c = node[0]
    edge, cost = node[i], node[i + 1]
    graph[c].append((edge, cost))

def bfs(s):
  visited = [-1] * (n + 1) # 방문하지 않으면 -1
  q = deque()
  q.append(s)
  visited[s] = 0
  max = [0,0]

  while q:
    x = q.popleft()
    
    for e, d in graph[x]:
      if visited[e] == -1:
        visited[e] = visited[x] + d
        q.append(e)

        if max[0] < visited[e]:
          max = visited[e], e
  
  return max

random_node = random.randrange(1, n + 1)
distance, node = bfs(random_node)
distance, node = bfs(node)
print(distance)

결과