BOJ 1967: 트리의 지름 [Python 3]

오늘의 문제는 웰-노운 문제 중 하나인 트리의 지름이다.

생각보다 방법만 알면 구현하기 쉬웠는데, 그 아이디어를 떠올리는게 너무 힘들었다.

deque를 이용해서 문제를 푼다,

먼저,  트리의 시작 노드부터 해서 BFS 탐색을 하는데, 모든 노드에 대해서 이동하면서, 값을 더해가면서 제일 말단의  branch node들 중 합이 제일 큰 node를 발견한다.

이 때, 그 해당 node에서부터 BFS탐색을 하는데, 거기서 최댓값이 정답이 된다.

이 문제의 해답을 알게 되고, 머리를 맞은 것 처럼 놀라웠다.

 

from collections import deque
import sys
input=sys.stdin.readline
def bfs(start):
    visited=[-1 for _ in range(n+1)]
    visited[start]=0
    q=deque()
    q.append([start,0])
    maximumVal=[0,0]
    while q:
        origin,dist=q.popleft()
        for next,value in tree[origin]:
            if visited[next]==-1:
                visited[next]=dist+value
                q.append([next,visited[next]])
                if maximumVal[1]<visited[next]:
                    maximumVal=[next,visited[next]]
    return maximumVal
n=int(input())
data=[list(map(int,input().split())) for _ in range(n-1)]
tree=[[] for _ in range(n+1)]
for a,b,num in data:
    tree[a].append([b,num])
    tree[b].append([a,num])
node,distance=bfs(1)
node,distance=bfs(node)
print(distance)