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

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

1967번: 트리의 지름

 

<풀이>

트리의 지름이란 두 점을 기준으로 길게 폈을 때 가장 길어지는 거리이다.

즉 기준이되는 두 점은 연결 노드가 한개다.

 

 

연결 노드가 한개인 점에서 다른 연결 노드가 한개인 점까지의 모든 길이를 비교해서 가장 긴 길이를 출력하면 된다.

 

 

 

<전체 코드>

 

import sys
from collections import deque

N = int(sys.stdin.readline())

tree = {i: [] for i in range(1, N+1)}

for _ in range(N-1):
    x, y, d = map(int, sys.stdin.readline().split())
    tree[x].append([y, d])
    tree[y].append([x, d])

radius = 0

for i in range(1, N+1):
    if len(tree[i]) == 1:
        queue = deque([[i, -1, 0]])

        while queue:
            now, prev, dis = queue.pop()

            if prev != -1 and len(tree[now]) == 1:
                if radius < dis:
                    radius = dis
            else:
                for next, next_dis in tree[now]:
                    if next != prev:
                        queue.append([next, now, dis+next_dis])

print(radius)