📚 문제
https://www.acmicpc.net/problem/1967
트리는 사이클이 없는 무방향 그래프이다.
모든 경로들 중에서 가장 긴 것을 트리의 지름이라고 한다.
문제에서 주어진 루트 노드는 1이다.
그림으로 어떻게 풀지 생각해본다.
후위 순회를 하며 자식노드부터 확인을 한다.
분기점에 도달하면 왼쪽에는 분기점에서 가장 긴 길이를 왼쪽에 적는다.
현재 분기점을 최상위 루트로 하는 트리 지름의 길이를 오른쪽에 적는다.
현재 노드가 분기점이 아니면 길이만 더해준다.
최상위 노드에서는 트리 지름의 길이만 적는다.
오른쪽에 적은 값들 중 가장 긴 지름의 값을 확인해보면 3번 노드가 루트 노드로 할 때 서브 트리에서의 트리의 지름이 현재 트리의 지름이 된다.
분기점에서 제일 긴 길이 두 개를 합하여 최댓값으로 업데이트한다. 실질적으로 계속 값을 저장해 갈 값은 왼쪽에 적는 다른 부모를 만날 때 활용할 최대 길이이다.
최대 길이도 저장하기보다는 재귀를 활용해 값을 더하면서 확인한다.
재귀 깊이 에러가 떠 깊이를 늘려줘 해결했다.
📒 코드
import sys
sys.setrecursionlimit(10000) # 재귀 깊이를 늘린다.
def recur(n):
global total_max
if arr[n] == []: # 자식 노드가 없으면 0을 반환
return 0
result = []
for c, w in arr[n]: # 자식 노드를 재귀호출하면서 가중치 값을 더해준다.
result.append(w + recur(c))
result.sort() # 노드에 연결된 길이들을 크기 순대로 정렬한다.
result = result[::-1][0:2] # 가장 긴 2개만 남긴다.
total_max = max(total_max, sum(result)) # 2개를 합한 것이 현재 구한 최대 트리의 지름보다 큰지 확인
return result[0] # 노드에 연결된 선 중 가장 긴 길이를 리턴
n = int(input())
arr = [[] for _ in range(n + 1)] # 부모 노드를 인덱스로 하는 리스트(자식노드와 가중치를 담는다.)
for i in range(n - 1):
p, c, w = map(int, input().split())
arr[p].append([c, w]) # 부모 노드의 리스트에 자식 노드와 그 때의 가중치를 리스트로 담는다.
total_max = 0 # 가장 긴 트리의 지름
recur(1)
print(total_max)🔍 결과
passionate developer