n-ary 트리가 주어졌을 때, 이 트리의 지름(diameter)을 구하는 문제를 생각해 봅시다. 여기서 트리의 지름이란 트리 내 임의의 두 리프 노드 사이에 존재하는 가장 긴 경로를 의미하며, 우리는 이 지름을 나타내는 정수 값을 계산하여 반환해야 합니다.
문제 예시
예를 들어 아래와 같은 트리가 입력으로 주어진다고 가정해 보겠습니다.
이 경우 출력은 3이 됩니다.
이 n-ary 트리의 지름은 27→14, 14→42, 그리고 42→56 또는 42→65로 이어지는 간선들로 구성됩니다(다이어그램에서 빨간 선으로 표시된 부분). 해당 경로의 길이는 3입니다.
해결 접근 방법
이 문제는 각 노드의 깊이를 재귀적으로 계산하면서, 동시에 두 개의 가장 긴 자식 경로를 합쳐 지름 후보를 갱신하는 방식으로 해결할 수 있습니다. 구체적인 단계는 다음과 같습니다.
전역 변수 ans를 1로 초기화합니다.
depth() 함수를 정의합니다. 이 함수는 노드(root)를 매개변수로 받습니다.
root가 비어 있다면 0을 반환합니다.
children 리스트를 [0, 0]으로 초기화하고, 임시 리스트 temp_children을 준비합니다.
root의 모든 자식 노드에 대해 depth(child)를 호출한 결과를 temp_children에 추가합니다.
temp_children의 크기가 0보다 크면 children을 temp_children으로 대체합니다.
children을 정렬한 뒤 마지막 두 요소(가장 긴 두 경로)의 합에 1을 더한 값과 ans를 비교하여 더 큰 값으로 갱신합니다.
children의 최댓값에 1을 더한 값을 반환합니다.
depth(root)를 호출한 뒤, 최종적으로 (ans - 1)을 반환합니다.
예제 코드 (Python)
아래 구현을 통해 더 자세히 이해해 보겠습니다.
class Node:
def __init__(self, value, child = None) -> None:
self.val = value
self.children = []
if child != None:
for value in child:
self.children.append(value)
ans = 1
def solve(root):
def depth(root):
global ans
if not root:
return 0
children = [0, 0]
temp_children = [depth(child) for child in root.children]
if len(temp_children) > 0:
children = temp_children
ans = max(ans, sum(sorted(children)[-2:]) + 1)
return max(children) + 1
depth(root)
return ans -1
node6 = Node(65)
node5 = Node(56)
node4 = Node(42, [node5, node6])
node3 = Node(32)
node2 = Node(27)
node1 = Node(14, [node2, node3, node4])
root = node1
print(solve(root))입력
node6 = Node(65) node5 = Node(56) node4 = Node(42, [node5, node6]) node3 = Node(32) node2 = Node(27) node1 = Node(14, [node2, node3, node4]) root = node1
출력
3