[백준 1967번] 트리의 지름 (Python3)

import sys
input = sys.stdin.readline
import heapq
INF = sys.maxsize

N = int(input())

graph = [[] for i in range(N+1)]

for i in range(N-1):
  x1,x2,w = map(int,input().split())
  graph[x1].append((x2,w))
  graph[x2].append((x1,w))

hq = []
distance = [[-INF]*(N+1) for i in range(2)]

def Dijkstra(node,distance):
  heapq.heappush(hq,(0,node))

  while hq:
    w,now = heapq.heappop(hq)
    if distance[now] >= w:
      continue
    distance[now] = w
    
    for i in graph[now]:
      x,weight = i
      heapq.heappush(hq,(w-weight,x))

Dijkstra(1,distance[0])
Dijkstra(1+distance[0][1:].index(min(distance[0][1:])),distance[1])
  
print(-min(distance[1][1:]))

 

다 익스트라 알고리즘으로 해결하였다. 아무 노드를 시작점으로 잡고 (보통 1), 해당 노드에서 가장 먼 노드를 찾고, 그 노드에서 가장 먼 노드를 찾아 거리를 구하면 그것이 곧 트리의 지름이다.

 

다익스트라 알고리즘은 최단거리를 찾도록 설계되어 있기에, heapq에 삽입할때 거리값을 음수로 넣어주어야 한다.

 

다 익스트라 알고리즘, 처음에 이와 관련된 문제를 보았을때는 풀이방법이 일주일 넘게 안떠올라 나를 끙끙대게 했었는데 (사실 지금 생각하면 안떠오르는게 당연하다) 알고 나면 너무나 편리한 알고리즘이 아닐 수 없다.

 

 

오늘의 교훈) 다 익스트라 알고리즘을 잘 활용하자