[Python] 백준 1167 트리의 지름

1167번: 트리의 지름

다익스트라 : 어떤 한 정점에서 가장 먼 곳의 정점은 가장 먼 두 정점 중 하나다. 문제의 핵심은 이것인데, 사실 잘 알기가 어렵다. 그래서 처음엔 DFS로 모든 경로의 거리값을 계산해 최댓값만 업데이트 시켰다. 이렇게 하면 시간초과와 메모리 초과가 발생하는데, 5까지 있다고 하면 1, 2, 3, 4, 5에서 출발하는 정점의 거리를 각각 찾아내기 때문에 이를 해결할 수 없다. 하지만, 처음 말했던 공식을 안다면, 어떤 한 정점이 무조건 포함됨을 알기에 그 정점을 우선 찾고, 그 정점으로 부터 가장 먼 정점까지의 거리를 알아내면 된다.

 

1) 다익스트라(정점 1) 출발을 해서 최대 먼 정점을 찾아낸다.

2) 다익스트라(정점 1로부터 최대 먼 정점) 출발을 해서 최대 먼 정점을 찾아낸다.

3) 찾아낸 정점의 최대 거리값을 출력한다.

 

전체코드

import sys
import collections
import heapq

input = sys.stdin.readline


def dijkstra(start):
    heap = []
    heapq.heappush(heap, (0, start))
    distance = [sys.maxsize for _ in range(V + 1)]
    distance[start] = 0

    while heap:
        cur_dis, cur_node = heapq.heappop(heap)
        if distance[cur_node] < cur_dis:
            continue
        for n, d in graph[cur_node]:
            next_dis = d + cur_dis
            if next_dis < distance[n]:
                distance[n] = next_dis
                heapq.heappush(heap, (next_dis, n))

    return distance


V = int(input())
graph = collections.defaultdict(list)

for i in range(1, V + 1):
    tmp = list(map(int, input().split()))
    for j in range(1, len(tmp), 2):
        if tmp[j] == -1:
            break
        graph[tmp[0]].append((tmp[j], tmp[j + 1]))

dis1 = dijkstra(1)
max_v1 = dis1.index(max(dis1[1:]))
dis2 = dijkstra(max_v1)
max_dis2 = max(dis2[1:])
print(max_dis2)