BOJ 1167 트리의 지름

접근 방법

인터넷 검색을 하니까 트리의 지름은 특이한 성질은 가진다고 한다. 임의의 점에서 제일 멀리 있는 노드는 무조건 트리 지름을 구성하는 끝 점 중 하나라고 한다. 따라서 dijkstra를 한번 하여 한 끝점을 구하고 그 끝점에서 dijkstra를 또 해서 지름을 구하였다.

정답 코드

import sys
from collections import deque
import heapq
input = sys.stdin.readline

v = int(input())
graph = [[] for _ in range(v+1)]
for _ in range(v):
    connects = list(map(int, input().split()))
    start = connects[0]
    idx = 1
    while connects[idx] != -1:
        graph[start].append((connects[idx], connects[idx+1]))
        idx += 2


"""
임의의 점에서 가장 먼 노드는 지름을 이루는 끝점이라고 한다.
bfs를 한번 하여 가장 먼 노드를 구한 다음, 
그 노드에서 가장 먼 노드까지의 거리를 구하면 트리의 지름을 구할 수 있음
"""

def dijkstra(start):
    distances = [sys.maxsize]*(v+1)
    distances[start] = 0
    q = [(0, start)]
    while q:
        mid_dist, mid_node = heapq.heappop(q)
        if mid_dist > distances[mid_node]:
            continue
        for end_node,end_dist in graph[mid_node]:
            new_dist = end_dist + distances[mid_node]
            if new_dist < distances[end_node]:
                distances[end_node] = new_dist
                heapq.heappush(q,(new_dist, end_node))
    return distances

start_point = 1
for vertex in range(1,v+1):
    if graph[vertex]:
        start_point = vertex
        break

distances = dijkstra(start_point)
distances = [0 if d == sys.maxsize else d for d in distances]
max_node = distances.index(max(distances))


distances = dijkstra(max_node)
distances = [0 if d == sys.maxsize else d for d in distances]
print(max(distances))