[ baekjoon ] 1167. 트리의 지름

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)
둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 매겨져 있다고 생각한다)

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데,
하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다.
각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

BFS를 이용해, 한 정점으로부터 가장 거리가 먼 정점번호와, 거리를 반환하도록 소스코드를 작성헀다.
여기서 BFS 알고리즘보다 더 핵심적인 내용을 알아야 이 문제를 풀 수 있을 듯하다
나는 처음에 모든 정점을 반복문으로 돌려, 가장 거리가 먼 값을 찾으려고 했지만 계속해서 시간 초과가 발생했다.
찾아보니, 트리의 지름을 빨리 구할 수 있는 내용이 존재했다.
트리의 지름은 트리의 임의의 한 점 x를 선택하고, x에서 가장 먼 정점 y를 찾은 후, 다시 y에서 가장 먼 정점 z를 찾으면, y와 z의 거리가 트리의 지름이 됨
이 내용만 알고 있다면, BFS 알고리즘과 선택 정렬을 활용해 쉽게 문제를 풀 수 있다!

## 트리의 지름
from collections import deque
import sys

input = sys.stdin.readline
v = int(input())

graph = [[] for i in range(v + 1)]
data = []
for _ in range(v):
  data = list(map(int, input().split()))
  vertex = data[0] 
  # v = data[0]했다가 index error 발생
  j = 1

  for _ in range((len(data) - 2)//2): 
  # == for j in range(1, len(data) - 1, 2): 와 같음
    graph[vertex].append((data[j], data[j + 1]))
    j += 2
result = 0

def bfs(x):
  visited = [False] * (v + 1)
  distance = [0] * (v + 1)

  q = deque(graph[x]) # 튜플 리스트

  for k in graph[x]:
    #print(k)
    if not visited[k[0]]:
      visited[k[0]] = True
      distance[k[0]] = k[1]
  visited[x] = True

  while q:
    now, cost = q.popleft()
    for k in graph[now]:
      if not visited[k[0]]:
        visited[k[0]] = True
        q.append(k)
        distance[k[0]] = max(distance[now] + k[1], distance[k[0]])

  max_idx = 0
  for i in range(1, len(distance)): # 선택 정렬
    if distance[max_idx] < distance[i]:
      max_idx = i
  
  return max_idx, distance[max_idx] # idx, value return
  
# 임의의 점을 선택해, 거리가 가장 먼 정점 번호 idx 찾기
idx, val = bfs(1) 
print(bfs(idx)[1]) # idx와 가장 거리가 먼 정점과의 거리