백준 - 그래프(# 1167)

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

Code

import sys

def dfs(node):
    for e,d in tree[node]:
        if dist[e] == 0:
            dist[e] = dist[node] + d
            dfs(e)

# make tree
n = int(input())
tree = {x:[] for x in range(1,n+1)}
for _ in range(n):
    inp = list(map(int, sys.stdin.readline().split()[:-1]))
    for i in range(1,len(inp)-1,2):
        tree[inp[0]].append([inp[i],inp[i+1]])

# find the farthest node from node 1
dist = [0]*(n+1)
dfs(1)
dist[1] = 0

farthest_node = 0
cnt = 0
for i in range(1,n+1):
    if dist[i] > cnt:
        cnt = dist[i]
        farthest_node = i

# find the farthest node from node 1
dist = [0]*(n+1)
dfs(farthest_node)
dist[farthest_node] = 0

result = 0
for i in range(1,n+1):
    if dist[i] > result:
        result = dist[i]
        farthest_node = i

print(result)  

참고

임의의 하나의 노드 A에서 가장 거리가 먼 노드 B를 구하고, 이 노드 B에서 가장 거리가 먼 노드 C를 구하면, B와 C 사이의 거리가 트리의 지름이 된다.