[BOJ] 1967 트리의 지름 - 그래프 이론, 다익스트라

www.acmicpc.net/problem/1967

1967번: 트리의 지름

 

'''
BOJ - 1967 트리의 지름 - 그래프 이론, 다익스트라
    그래프와는 조금 색다른 트리의 지름이다. 기본 로직은 그래프의 지름과 같다. 똑같이 다익스트라를 이용하여 계산해주면 되는데
    이 문제가 더 쉬운게 루트노드부터 입력하므로 항상 1번 노드가 루트 노드이다. 그래서 1번에서 가장 먼 노드를 구한 후 그 노드에서
    가장 먼 노드를 구하면 된다.
'''
import sys, math
 
 
def dikstra(num): # 다익스트라 계산 함수
    queue = [num]
    while queue:
        node = queue.pop(0)
        for i in graph[node]:
            if distance[i[0]] > distance[node] + i[1]:
                distance[i[0]] = distance[node] + i[1]
                queue.append(i[0])
 
 
n = int(sys.stdin.readline())
graph = [[] for _ in range(n+1)] # 간선 weight 저장 함수
 
for _ in range(n - 1):
    p, c, v = map(int, sys.stdin.readline().split(" "))
    # 노드 간 간선 정보 저장
    graph[p].append([c, v])
    graph[c].append([p, v]) 
 
# 1에서 가장 먼 노드를 찾는다
# 1번 노드에서 각 노드와의 거리
distance = [math.inf for _ in range(n + 1)]
distance[1] = 0
# 거리 계산
dikstra(1)
# 인덱스 0번 제거 처리
distance = distance[1:]
# 가장 먼 노드를 계산한다
max_num_one = distance.index(max(distance)) + 1
# 그 노드에서 가장 먼 노드를 구한다.
distance = [math.inf for _ in range(n + 1)]
distance[max_num_one] = 0
dikstra(max_num_one)
distance = distance[1:]
print(max(distance))