[백준 1967] 트리의 지름 - 파이썬 풀이 (골드4)

https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

---

 

문제 요약

트리를 입력 받아서 해당 트리의 지름을 구하여라.

---

풀이

트리의 지름은 임의의 정점에서 출발하여 최단거리로 갈 수 있는 노드를 구하고, 그 노드에서 다시 최단 거리로 갈 수 있는 노드까지의 거리가 된다.
양의 가중치가 있는 트리가 입력으로 주어지므로, 양의 가중치 그래프에서 최단거리를 탐색할 때 활용할 수 있는 다익스트라 알고리즘을 활용한다. 처음 출발하는 임의의 노드는 root인 1로 설정하고, 첫 번째로 도착하는 최단 거리 지점을 first_end라고 명명하였다. 그리고 이 first_end에서 출발하여 도달할 수 있는 지점 second_end까지의 최단거리인 second_dist를 정답으로 제출하였다.

# 백준 1967 트리의 지름 골드4 https://www.acmicpc.net/problem/1967
import heapq
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b, w = map(int, input().split())
    graph[a].append((b, w))
    graph[b].append((a, w))

def dij(start):
    q = []
    distance = [1e9] * (n+1)
    distance[start] = 0
    heapq.heappush(q, (0, start))
    while q:
        dist, node = heapq.heappop(q)
        for next_node, next_dist in graph[node]:
            cost = dist + next_dist
            if cost < distance[next_node]:
                distance[next_node] = cost
                heapq.heappush(q, (cost, next_node))
    return node, dist

first_end, first_dist = dij(1)
second_end, second_dist = dij(first_end)
print(second_dist)