[백준] 1967번: 트리의 지름

문제

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

1967번: 트리의 지름

 

풀이

DFS(깊이 우선 탐색)를 사용해 풀었습니다.

양방향 간선이므로 graph의 부모, 자식 노드에 해당하는 공간에 서로를 가중치와 함께 추가합니다.
트리의 지름을 구하는 방법은 다음과 같습니다.

1. 루트 노드로부터 거리가 가장 먼 노드를 구합니다.
2. 구한 노드로부터 거리가 가장 먼 노드까지의 거리를 구합니다.

 

코드

파이썬

import sys

sys.setrecursionlimit(10**6)

input = sys.stdin.readline

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

for _ in range(n - 1):
    n1, n2, w = map(int, input().split())
    graph[n1].append((n2, w))
    graph[n2].append((n1, w))


def DFS(x, w):
    for nx, nw in graph[x]:
        if distance[nx] == -1:
            distance[nx] = w + nw
            DFS(nx, distance[nx])


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))