백준 1967번: 트리의 지름

BOJ

백준 1967번: 트리의 지름

접근

트리(tree)는 사이클이 없는 무방향 그래프이다. 트리의 지름이란 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.

처음에 무조건 루트에서 시작해서 왼쪽 끝과 오른쪽 끝까지의 가중치의 합이 가장 큰 값이지 않을까 생각했는데, 문제에 나와 있는 예제를 보고 꼭 그럴 필요가 없음을 알았다.

트리의 지름은 dfs(or bfs) 두 번을 통하여 간단하게 O(n)의 시간복잡도로 구현이 가능하다.

Correct Solution

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**9)

N = int(input())
graph = [[] * N for _ in range(N+1)]


def dfs(node, wei):
    for i in graph[node]:
        child, weight = i
        if distance[child] == -1:
            distance[child] = wei + weight
            dfs(child, wei + weight)


for _ in range(N - 1):
    P, C, W = map(int, input().split()) # parent, child, weight
    graph[P].append([C, W])
    graph[C].append([P, W])

# 1번 노드에서 가장 먼 곳을 찾는다.
distance = [-1] * (N + 1)
distance[1] = 0
dfs(1, 0)

# 위에서 찾은 노드에서 가장 먼 곳을 찾는다.
start = distance.index(max(distance))
distance = [-1] * (N + 1)
distance[start] = 0
dfs(start, 0)

print(max(distance))

참고 사이트

Kyun2Da Blog 구사과