[python] 1167 - 트리의 지름

1167번: 트리의 지름 (acmicpc.net)

1167번: 트리의 지름

트리의 지름이란?

트리의 모든 경로들 중 가장 긴 경로의 길이를 의미한다.

문제 자체는 dfs나 bfs 로 구현하면 되는 문제였는데

트리의 지름을 구하기 위해 필요한 공식이 있었다.

 

트리의 지름이 u-v라고 할 때, 임의의 점 x에서 가장 먼 노드는 u 또는 v가 된다.

따라서 임의의 노드에서 가장 먼거리에 있는 노드를 찾고

그 노드에서 다시 가장 먼 거리의 노드를 찾으면

트리의 지름을 찾을 수 있다.

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

v = int(input())
graph=[[] for i in range(v+1)]

for i in range(v):
    line = list(map(int, input().split()))
    root = line[0]
    idx = 1
    while line[idx] != -1:
        node = line[idx]
        cost = line[idx+1]
        graph[root].append((node, cost))
        idx+=2
        
def BFS(start):
    q = deque()
    q.append((start, 0))
    visited = [-1]*(v+1)
    visited[start] = 0
    rst = [0, 0] 
    
    while q:
        now, cost = q.popleft()
        
        for adj_node, adj_cost in graph[now]:
            if visited[adj_node] == -1:
                total = cost + adj_cost
                q.append((adj_node, total))
                visited[adj_node] = total
                if rst[1] < total:
                    rst[0] = adj_node
                    rst[1] = total
        
    return rst

s,e = BFS(1)
print(BFS(s)[1])