[CLASS 4]백준 1967번 - 트리의 지름

1967번 : 트리의 지름

 

이 문제를 풀기 위한 핵심 아이디어만 알았다면 쉽게 풀 수 있다.

 

문제에 힌트가 나와 있는데, 트리의 지름의 양 끝에 해당하는 두 노드를 선택해서 양쪽으로 당기면 나머지 노드들은 해당 원 안에 들어가게 된다고 나와 있다.

 

여기서 얻을 수 있는 힌트는, 트리 내의 임의의 노드에서 가장 먼 노드를 구하면, 해당 노드는 무조건 지름의 양 끝 중 하나라는 것이다.

 

이를 몰랐다면 풀기 매우 힘든 문제가 될 수 있다.(나처럼...) 이를 눈치챘다면 쉽게 풀 수 있다.

 

내 코드:

# dawitblog.tistory.com/153
from sys import stdin,setrecursionlimit
input = stdin.readline
# 재귀깊이 설정
setrecursionlimit(10**9)

def dfs(node):
    global start_point
    for next_node,cost in nodes[node]:
        if not distances[next_node] and next_node != start_point: # 시작점은 0으로 유지
            distances[next_node] = distances[node] + cost
            dfs(next_node)


n = int(input())
nodes = [[] for _ in range(n+1)]
for _ in range(n-1):
    a,b,c = map(int,input().split())
    nodes[a].append((b,c))
    nodes[b].append((a,c))

distances = [0] * (n+1)
# 임의의 점에서 시작
start_point = 1
# 가장 먼 노드 탐색
dfs(start_point)

max_dis = 0
point_one = -1
for i in range(1,n+1):
    if distances[i] > max_dis:
        max_dis = distances[i]
        point_one = i

distances = [0] * (n+1)
# 가장 먼 노드에서 가장 먼 노드 탐색
start_point = point_one
dfs(start_point)

print(max(distances))

 

양방향 그래프로 만들어 놓고, DFS를 임의의 점(루트 노드로 했으나 다른 노드도 상관 X)에서 한번 돌려서 가장 먼 노드를 찾고,

이 노드에서 DFS를 한번 더 돌려서 가장 긴 길이를 찾으면 그게 트리의 지름이다.