[Baekjoon] 1167번 트리의 지름

문제

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

 

풀이

지난번에 풀었던 1967번 트리의 지름을 그대로 이용한 문제 풀이다.

트리의 지름은 하나의 공식처럼 이해하면 좋을 것 같다.

    1. 루트 노드에서 각 노드까지 최소 거리를 구한다.

    2. 최소 거리가 가장 먼 노드에서 가장 먼 거리를 구한다.

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

v = int(input())
nodes = [[] for _ in range(v+1)]

for _ in range(v):
    q = deque(list(map(int, input().split())))
    x = q.popleft()

    while q:
        y = q.popleft()
        if y == -1:
            break
        
        w = q.popleft()
        nodes[x].append((y, w))
        nodes[y].append((x, w))
    
def bfs(i):
    visited = [-1] * (v+1)
    visited[i] = 0
    q = deque()
    q.append(i)

    while q:
        cur = q.popleft()
        for next, next_d in nodes[cur]:
            if visited[next] == -1:
                q.append(next)
                visited[next] = visited[cur] + next_d
    
    m = max(visited)
    return [visited.index(m), m]

print(bfs(bfs(1)[0])[1])