[BOJ/백준] 1967 트리의 지름

import sys
sys.setrecursionlimit(10000)
def dfs(node):
    if not graph[node]:
        return 0
    ind = 0
    for next_node in graph[node]:
        distance_nodes[node][ind] += dfs(next_node) + graph[node][next_node]
        ind += 1
    return max(distance_nodes[node])
N = int(input())
graph = [{} for _ in range(N+1)]
parents = [0]*(N+1)
for _ in range(N-1):
    A,B,C = map(int,input().split())
    graph[A][B] = C
    parents[A] += 1

distance_nodes = [[0]*(parents[ind]+2) for ind in range(N+1)]

dfs(1)
result = 0
for ind in range(1,N+1):
    distance_nodes[ind].sort(reverse=True)
    result = max(result,distance_nodes[ind][0]+distance_nodes[ind][1])
print(result)

첫 풀이방식은 다음과 같았다. 각 노드에서 가장 긴 노드들을 더해주는 방식이었다. 리프노드에 도착하면 0을 반환해주고 

 

재귀를 활용해서, 현재의 노드에서 자식노드까지의 거리 + 그 자식노드의 재귀함수를 통해 최대값을 더해주는 방식으로 했다.

 

이렇게 모든 노드들에 대해서 거리들을 전부 구한뒤, 모든 노드들의 거리의 합이 최대가 되는것을 구해주었다.

 

import sys
input = sys.stdin.readline
def dfs(ind):
    global N,result,max_Node
    visited = [True]*(N+1)
    stack = []
    stack.append((ind,0))
    visited[ind] = False
    while stack:
        node, distance = stack.pop()
        if distance > result:
            result = distance
            max_Node = node
        if graph[node]:
            for next_node in graph[node]:
                if visited[next_node]:
                    visited[node] = False
                    stack.append((next_node,distance+graph[node][next_node]))


N = int(input())
graph = [{} for _ in range(N+1)]
for _ in range(N-1):
    A,B,C = map(int,input().split())
    graph[A][B] = C
    graph[B][A] = C

result = 0
max_Node = 0

dfs(1)
dfs(max_Node)
print(result)

두번째 방식은 훨씬 간단하다. 두번의 dfs로 풀리는데 다음과 같다.

어느 한 지점에서 제일 거리가 멀리 떨어진 곳에 위치 한 곳을 구하면, 그 지점이 트리의 지점을 구할 수 있는 한 점인 것을 알 수 있다.

 

왜냐하면, 지름은 해당 트리에서 제일 긴 곳은 지름일테고, 그렇기 때문에 그 안에 있는 점의 가장 먼거리를 가지는 점은 지름의 두 점 중 하나가 될것이다.

 

이걸 이용해서 첫번째 dfs에서 트리의 지름에 해당하는 한 점을 구하고,

 

그 점에서 dfs를 통해 최대거리를 구하면 답이 된다.