[Baekjoon] 1167. 트리의 지름

🔗 Problem Link

1167번: 트리의 지름

---

❔Thinking

• 트리는 한 노드에서 다른 노드까지 가는 경로가 유일하다.
• 한 노드에서 가장 먼 노드는, 트리의 지름의 한 양 지점 중 하나이다.

---

💻Solution

import sys
import heapq
input = sys.stdin.readline
V = int(input())
tree = [[] for _ in range(V+1)]
for _ in range(V):
    tmp = list(map(int, input().split()))
    s = tmp[0]
    for i in range(1, len(tmp)-1, 2):
        tree[s].append((tmp[i+1], tmp[i]))
        tree[tmp[i]].append((tmp[i+1], s))


def dijkstra(start):
    distance = [int(1e9) for _ in range(V+1)]
    distance[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        cost, now = heapq.heappop(q)
        if distance[now] < cost:
            continue
        for i in tree[now]:
            if distance[i[1]] > cost + i[0]:
                distance[i[1]] = cost + i[0]
                heapq.heappush(q, (i[0]+cost, i[1]))
    return distance[1:]

distance_a = dijkstra(1)
b = 0
b_dist = 0
for node, dist in enumerate(distance_a, start=1):
    if b_dist < dist:
        b = node
        b_dist = dist
print(max(dijkstra(b)))

---

🗝️keypoint

1. 다익스트라는 그래프에서 최단 거리를 찾는 알고리즘이다. 트리도 그래프 구조이므로 활용 가능하다.
2. 트리는 임의의 노드에서 다른 노드로 가는 경로가 유일하기 때문에, bfs를 활용해도 위와 같은 결과를 얻을 수 있다.
3. 트리에서 임의의 노드에서 가장 먼 거리의 노드를 찾으면, 트리 지름의 한 노드이다.