난이도 : 골드 4
유형 : 트리
https://www.acmicpc.net/problem/1967

문제

트리의 지름 구하는 문제이다.

트리의 지름 구하는 문제 는 풀어봤다.
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):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    graph[v].append((u, w))

def bfs(start):
    visited = [-1] * (n + 1)
    visited[start] = 0
    q = deque([start])

    while q:
        now = q.popleft()
        for next, dist in graph[now]:
            if visited[next] == -1:
                visited[next] = visited[now] + dist
                q.append(next)
    
    # 가장 멀리 있는 노드와 그 거리 리턴
    max_dist = max(visited)
    max_node = visited.index(max_dist)
    return max_node, max_dist

# 1. 임의의 노드 (1번)에서 가장 먼 노드 A를 찾는다
a, _ = bfs(1)

# 2. A에서 가장 먼 노드까지 거리 = 지름
_, diameter = bfs(a)

print(diameter)

입력 로직이 더 단순했던 , 전에 풀었던 문제보다 더 수월했던 문제였다.