[백준] 1967번 트리의 지름 - Python

이번에 해결해 볼 문제는 백준에 있는 1967번 트리의 지름입니다.

---

문제 설명

1. 트리에서 두 노드의 거리를 트리의 지름이라고 합니다.
2. 트리의 지름이 가장 긴 것을 출력하면 됩니다.

문제 해결 아이디어

• 임의의 노드에서 가장 멀리 있는 노드를 선택하고 해당 노드에서 가장 멀리 있는 노드를 다시 한 번 찾으면 트리의 지름이 됩니다.
  • 위의 아이디어를 사실 모른다면 풀 수 없는 문제로 이런 것은 기억할 필요가 있을 것 같습니다.
• 트리의 거리를 구하는 문제이므로 DFS 또는 BFS를 사용할 수 있습니다.
• 두 번의 거리를 구해야 하므로 DFS 또는 BFS를 두 번 사용하면 됩니다.

문제 해결 코드

import sys

from collections import deque

input = sys.stdin.readline

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

for _ in range(n - 1):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))


def bfs(graph, start, visited):
    queue = deque([(start, 0)])
    visited[start] = -1

    while queue:
        v, cost = queue.popleft()
        for i, next_cost in graph[v]:
            if visited[i] == 0:
                queue.append((i, cost + next_cost))
                visited[i] = cost + next_cost


# 임의의 노드에서 가장 먼 노드 찾기 (BFS - 1)
visited = [0] * (n + 1)
bfs(graph, 1, visited)

max_val = 0
max_idx = 0
for i in range(1, n + 1):
    if visited[i] > max_val:
        max_val = visited[i]
        max_idx = i

# 위에서 찾은 노드에서 가장 먼 노드 찾기 (BFS - 2)
visited = [0] * (n + 1)
bfs(graph, max_idx, visited)
print(max(visited))