[백준] 1967 트리의 지름 : 다익스트라를 응용하자 !

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

1967번: 트리의 지름

 

트리도 결국 그래프에 속한다! 라고 생각하면 조금 더 쉽다 

모양은 나무처럼 생겨서 이상하지만,, 

결국 우리는 1번 노드에서 가장 멀리 떨어진 정점을 찾고, 그 정점에서 가장 멀리 떨어진 정점을 찾아서 

두 가중치를 더해주면 최대값이 된다 

 

이 예시에서도 1번에서 가장 떨어진 노드는 9번이다. 이말은 노드 1에서 출발 했을 때 가중치 값이 가장 큰 노드가 9라는 것이다 

그후 9번을 기준으로 다익스트라 함수를 실행시키고 maximum 가중치 값을 구한다 -> 이 예시에서는 9에서는 12가 가장 멀다 

그리고 두 비용을 더해주면 끝!!! 

 

# 1967 트리의 지름
import heapq

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

def dijkstra(start):
    distance = [INF]*(n+1)
    distance[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        cost, now = heapq.heappop(q)
        for next, next_cost in graph[now]:
            dist = next_cost + cost
            if dist < distance[next]:
                distance[next] = dist
                heapq.heappush(q, (dist, next))
    return distance
result = dijkstra(1)
first = max(result[1:])
print(max(dijkstra(result.index(first))[1:]))