[Baekjoon/python] 트리의 지름 #1167

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

1167번: 트리의 지름

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

코드

• 다익스트라 알고리즘 적용
• 거리를 음수로 사용하여 최단거리문제로 정의
• 풀이 참고 + 주석 설명 참고

import sys
import heapq
from collections import defaultdict


def dijkstra(graph, v, src):
    heap = [(0, src)]
    visited = set()
    min_dist = [1001] * v
    while heap:
        cur_weight, cur_node = heapq.heappop(heap)
        min_dist[cur_node] = cur_weight
        visited.add(cur_node)
        if len(visited) == V:
            return min_dist.index(min(min_dist)), min(min_dist)
        for nxt_node, nxt_weight in graph[cur_node]:
            if nxt_node in visited:
                continue
            heapq.heappush(heap, (cur_weight + nxt_weight, nxt_node))

input = sys.stdin.readline

V = int(input())
graph = defaultdict(list)
for _ in range(V):
    line = list(map(int, input().split()))
    cur_node, edges = line[0], line[1:-1]
    nxt_node, weight = 0, 1
    while weight < len(edges):
        graph[cur_node].append([edges[nxt_node], -edges[weight]])
        nxt_node += 2
        weight += 2

# 1. 임의의 노드에서 가장 먼 노드 탐색
# 2. `1`에서 구한 노드에서 가장 먼 노드 탐색
# 3. `2`에서 구한 노드에서 구한 가장 먼 거리가 최대 지름
node1, _ = dijkstra(graph, V + 1, 1)
_, min_weight = dijkstra(graph, V + 1, node1)
print(-min_weight)