1167_트리의지름

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

1167번: 트리의 지름

 

 

 

트리구조를 활용한 문제이다.

 

만약 트리의 어떠한 노드를 무작위로 잡는다고 생각해보자. 그점에서 가장 먼 곳을 잡는다면 한방향으로만 갈수있는 트리방향 특성상 가장 하단이거나 가장 상단일 것이다.

 

그 점에서 다시 최장거리를 구한다면 결국 트리전체구조의 최장거리를 구할 수 있다.

 

 

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

v = int(input())
graph = [ [] for _ in range(v+1)]
for _ in range(v):
    c = list(map(int, input().split()))
    for e in range(1, len(c) - 2, 2):
        graph[c[0]].append((c[e], c[e + 1]))


def bfs(start):
    visit = [-1] * (v+1)
    q = deque()
    q.append(start)
    visit[start] = 0
    result = [0,0]

    while q:
        node = q.popleft()
        for e,w in graph[node]:
            if visit[e] == -1:
                visit[e] = visit[node] + w
                q.append(e)
                if result[0] < visit[e]:
                    result = [visit[e],e]

    return result

dist , node = bfs(1)
dist , node = bfs(node)
print(dist)