[백준 1967 / Python] 트리의 지름

난이도: 골드4

분류: 그래프 이론, 그래프 탐색, 트리, 깊이 우선 탐색

 

key point

• leaf node - leaf node는 불가능. leaf가 하나인 경우도 존재하고, parent - child의 거리가 더 먼 경우도 충분히 존재한다
• 트리의 지름 안에 모든 다른 점들이 위치해있다. 따라서 어떤 점에서 탐색하든 상관없이 가장 멀리있는 정점을 고른다면, 그 점은 트리 지름 노드 중 하나이다
• 그리고 트리 지름 노드에서 가장 먼 정점은, 또 다른 트리 지름 노드가 된다

 

fst approach (x)

• 우선순위 큐를 사용
• cost가 높은 순서대로 차례대로 꺼냈을 때, 가장 먼저 나오는 두 개의 leaf node를 연결한 비용이 트리의 지름이다

>>> fail, cost가 가장 높더라도 정답이 아닌 경우가 충분히 존재한다

 

sec approach (o)

• hint: https://www.acmicpc.net/board/view/136998
• key point를 따라서 해결
• dijkstra를 두 번 사용해서 해결했음

from heapq import *
from sys import stdin
input = stdin.readline

n = int(input())
graph = [[] for _ in range(n+1)]
for i in range(n-1):
    p, c, cost = map(int,input().split())
    graph[p].append((c, cost))
    graph[c].append((p, cost))

# 예외처리
if n == 1:
    print(0)
    exit()

# 다익스트라로 최대거리 탐색 *2
def dijkstra(stt):
    diameterNode = 1
    distance = [int(1e9)]*(n+1)
    distance[0] = 0
    distance[stt] = 0
    hq = []
    hq.append((0,stt))
    while hq:
        dist, node = heappop(hq)
        if distance[node] < dist:
            continue
        for data in graph[node]:
            neighbor = data[0]
            cost = distance[node] + data[1]
            if cost < distance[neighbor]:
                distance[neighbor] = cost
                heappush(hq, (cost, neighbor))
    maxDist = max(distance)
    diameterNode = distance.index(maxDist)
    return diameterNode, maxDist

diameterNode, maxDist = dijkstra(1)
print(dijkstra(diameterNode)[1])