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

백준 1967번

최종 제출 코드

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

n = int(input().rstrip())
terminal = [False] + [True]*n
terminal_node = []
array = [[] for i in range(n+1)]
distance = {}
for i in range(1, n+1):
  distance[i] = {}

for i in range(n-1):

  parent, child, weight = map(int, input().split())
  array[parent].append(child)
  array[child].append(parent)
  distance[parent][child] = weight
  distance[child][parent] = weight
  terminal[parent] = False

for i in range(1, len(terminal)):
  if terminal[i] == True:
    terminal_node.append(i)
    


def bfs(start_node):

  queue = deque()
  queue.append(start_node)
  visited = [-1] * (n+1)
  visited[start_node] = 0

  while queue:

    node = queue.popleft()

    for i in range(len(array[node])):
      if visited[array[node][i]] == -1:
        visited[array[node][i]] = visited[node] + distance[node][array[node][i]]
        queue.append(array[node][i])

  result = max(visited)
  return [visited.index(result), result]


node = bfs(terminal_node[0])[0]
max_distance = bfs(node)[1]
  
print(max_distance)

◼️ 그래프의 간선을 저장하는 array리스트와 노드 간 거리를 저장하는 distance리스트를 생성
.

◼️ terminal node를 구한다

• 그래프 내에서 최대 거리에 속하는 두 개의 노드는 그래프의 terminal node일 수밖에 없음
• 입력값에서 부모노드로 등장하지 않는 노드들이 terminal node
• terminal 리스트에 True값을 저장하고 부모 노드로 등장하는 노드들은 False로 값을 바꿈
  ⇒ 가장 처음 등장하는 True의 인덱스값을 terminal_node에 저장
  (terminal node는 한 개만 구해도 됨)

.
◼️ BFS 실행

• 먼저 terminal_node를 시작노드로 해서 BFS를 실행한 후, 반환된 노드에 대해 한 번 더 BFS를 실행하면 정답 도출