BaekJoon 1167번 : 트리의 지름 (python)

BaekJoon 1167번 : 트리의 지름 (G2 33.981%)

트리의 지름 문제

이번에는 BFS or DFS를 두 번 이용하여 가장 긴 길이를 찾는 문제이다.

• 먼저 임의의 한 정점을 지정해서 해당 정점에서 가장 멀리 떨어져있는 정점을 BFS를 통해 찾아준다. 여기서는 정점 1을 시작으로 찾아주게 된다.
• BFS에서는 1부터 각 정점까지의 떨어져있는 거리를 q에 담아 반복하게 되고 각 정점까지의 길이중 가장 최대가 되는 정점의 index를 찾아준다. 이 때 첫번째 BFS에서 발견한 노드는 트리의 한 끝점 A를 나타내게 된다.
• 찾은 해당 정점에서 다시 BFS를 출발하여 각 정점까지의 거리를 계산해주고 거리가 최대가 될 때마다 해당 index를 갱신해주며 다시 한 번 가장 멀리 떨어져있는 노드의 거리를 계산할 수 있게 된다. 이때의 노드 B는 끝점 A로부터 가장 멀리 떨어진 트리의 다른 끝점을 나타내게 된다.
• 이 방법은 트리의 모든 노드를 두번 탐색함으로써 최대 거리(지름)을 정확히 찾을 수 잇다. 이 두 노드 사이의 경로가 가장 긴 경로가 되며, 트리의 구조상 다른 모든 경로는 이보다 짧거나 같다.

import sys
from collections import deque
input = sys.stdin.readline

def bfs(start) :
    q = deque()
    q.append((start,0))
    distance = [-1]*(n+1)
    distance[start] = 0
    temp = (0,0)
    while q :
        x, current = q.popleft()
        for i, dis in node[x] :
            if distance[i] == -1 :
                distance[i] = current + dis
                q.append((i,distance[i]))
                if distance[i] > temp[1] :
                    temp = (i, distance[i])

    return temp
n = int(input())
node = [[] for _ in range(n+1)]
for _ in range(n) :
    s = list(map(int,input().split()))
    a = s[0]
    for i in range((len(s)-2)//2) :
        b = s[i*2+1]
        c = s[i*2+2]
        node[a].append((b,c))
temp = bfs(1)
result = bfs(temp[0])
print(result[1])