[백준] 1167번(트리의 지름)

백준 1167번

최종 제출 코드

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

n = int(input().rstrip())
distance = {}
queue = deque()


for k in range(n):
  
  elements = list(map(int, input().split()))
  node = elements[0]
  sub = {}
  
  for i in range(1, len(elements)-1, 2):
    linked_node = elements[i] #노드
    path = elements[i+1] #간
    sub[linked_node] = path
    
  distance[node] = sub


def bfs(index):

  visited = [-1 for _ in range(n+1)]
  queue.append(index)
  visited[index] = 0
  
  while queue:
  
    node = queue.popleft()
  
    for i in distance[node]:
      if visited[i] == -1:
        visited[i] = visited[node] + distance[node][i]
        queue.append(i)

  max_distance = max(visited)
  return [max_distance, visited.index(max_distance)]
  
node = bfs(1)[1]
result = bfs(node)[0]
print(result)

◼️ BFS 호출 최소화하기

• 처음에는 모든 노드의 모든 노드에 대한 거리를 구함
  ⇒ BFS만 n*n번 호출
  ⇒ 시간초과

• 해당 코드를 참고하여 수정
  ▫️ 임의의 노드 1개에 대해 BFS를 실행해서 가장 멀리에 있는 노드를 구함
  ▫️ 그 노드에 대해 한 번 더 BFS를 실행하여 최대거리를 구함
  ⇒ 이렇게 하면 BFS를 두 번만 실행해도 됨