[백준] G4. boj1967 트리의 지름 / 분류 : 트리, dfs 😑

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

1967번: 트리의 지름

트리의 지름 구하기

1. 트리의 아무 노드에서 시작해서 dfs를 수행하여 가장 길이가 먼 노드를 구한다. 그럼 그 노드가 리프 노드가 된다.
2. 앞에서 찾은 리프 노드에서 동일한 dfs를 수행하여 가장 긴 길이가 지름이 된다.

import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

N = int(input())

graph = [[] for _ in range(N+1)]
for i in range(N-1):
    parent, child, dist = map(int, input().split())
    graph[parent].append((child, dist))
    graph[child].append((parent, dist))

dists = [-1] * (N+1)
dists[1] = 0
def dfs(n, dist):
    for node in graph[n]:
        c, d = node[0], node[1]
        if dists[c] == -1:
            dists[c] = dist + d
            dfs(c, dist + d)

dfs(1, 0)

start = dists.index(max(dists))
dists = [-1] * (N+1)
dists[start] = 0
dfs(start, 0)

print(max(dists))

방문 처리를 dists 배열로 하였다. dists 배열은 각 노드까지의 거리를 저장한다. 시작 노드의 거리를 0으로 초기화하고 dfs를 시작한다. 

1에서 첫 dfs를 수행했고, 이를 통해 리프노드를 구해서 또 한번 dfs를 수행했다.