[DFS, BFS] 백준 1167번: 트리의 지름 / 골드 3

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

1167번: 트리의 지름

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지

www.acmicpc.net

import collections
n = int(input())
graph = collections.defaultdict(list)

for i in range(n):
    row = list(map(int, input().split()))
    start = row[0]
    for j in range(1, len(row)-1, 2):
        next, w = row[j], row[j+1]
        graph[start].append([next, w])


global val
global max_node
val, max_node = 0, 0

def dfs(node, weight):
    global val
    global max_node

    if val < weight:
        val = weight
        max_node = node

    for next, w in graph[node]:
        if not visited[next-1]:
            visited[next-1] = True
            dfs(next, weight + w)


visited = [False for _ in range(n)]
visited[0] = True
dfs(1, 0)

visited = [False for _ in range(n)]
visited[max_node-1] = True
dfs(max_node, 0)

print(val)

트리의 지름 구하는 공식을 알고 있으면 구현은 쉽지만, 그 공식을 모르면 풀기가 힘들다.

<트리의 지름 구하는 공식>

임의의 노드에서 거리가 가장 긴 노드를 구함(그럼 이 도착 노드가 트리의 지름을 구성하는 양 끝 노드 중 한 노드임)

이 노드에서 다시 거리가 가장 긴 노드를 구함. 이때의 거리가 트리의 지름이 된다.