[백준] 1167번 트리의 지름 - 파이썬/트리

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

V = int(input())

graph = [[] for _ in range(V + 1)]


for i in range(V):
    temt = list(map(int,input().split()))

    N = temt[0]


    for j in range(1,len(temt),2):
        elem = temt[j:j+2]

        if elem==[-1]:
            break
        else:
            graph[N].append(elem)


distance = [-1] * (V + 1)
distance[1] = 0

def dfs(x, wei):
    for i in graph[x]:
        a, b = i
        if distance[a] == -1:
            distance[a] = wei + b
            dfs(a, wei + b)

dfs(1,0)


start = distance.index(max(distance))

distance = [-1] * (V + 1)
distance[start] = 0
dfs(start, 0)

print(max(distance))

그 전에 풀었던 문제와 유사했다.

트리의 지름을 구하는 방식은 아래의 2가지 순서로 이루어 진다.

1. 임의의 노드에서 가장 먼 거리의 노드를 구한다.

2. 1에서 구한 노드와 가장 멀리 떨어진 노드와의 거리를 구한다.

여기서 구한 거리가 트리의 지름이다.