배열 형태로 N-ary 트리(다진 트리)의 노드들이 주어졌다고 가정해 봅시다. 이때 트리를 재구성하여 루트 노드를 찾아 반환해야 합니다. 그리고 반환된 루트 노드로부터 전체 트리를 전위 순회(preorder) 방식으로 출력하면 됩니다.
예를 들어 입력이 다음과 같다고 해보겠습니다.
그렇다면 출력은 다음과 같습니다.
[14, 27, 32, 42, 56, 65]
찾은 루트 노드를 기준으로 트리의 전위 순회(preorder traversal)를 수행하기 때문에, 최종 출력값은 트리의 전위 순회 결과가 됩니다.
문제 해결 접근 방법
이 문제는 진입 차수(indegree) 개념을 활용하면 간단하게 해결할 수 있습니다. 루트 노드는 부모가 없는 유일한 노드이므로, 어떤 노드도 자식으로 가리키지 않는 노드가 곧 루트입니다. 구체적인 단계는 다음과 같습니다.
정수 값을 저장하는 새로운 맵(map)으로 indegree를 초기화합니다.
트리의 각 노드에 대해:
해당 노드의 자식 포인터들을 순회하며 각 자식의 진입 차수를 1씩 증가시킵니다.
indegree[자식의 값] := indegree[자식의 값] + 1
트리의 각 노드를 다시 순회하며:
indegree[노드의 값]이 0이라면 해당 노드가 루트이므로 즉시 반환합니다.
루트를 찾지 못했다면 null을 반환합니다.
Python 구현 예제
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
import collections
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)
def solve(tree):
indegree = collections.defaultdict(int)
for node in tree:
for child in node.children:
indegree[child.val] += 1
for node in tree:
if indegree[node.val] == 0:
return node
return None
def treeprint(node, tree):
if node == None:
tree.append("None")
return tree
if tree == None:
tree = []
tree.append(node.val)
for child in node.children:
treeprint(child, tree)
return tree
node6 = Node(65)
node5 = Node(56)
node4 = Node(42, [node5, node6])
node3 = Node(32)
node2 = Node(27)
node1 = Node(14, [node2, node3, node4])
tree = [node2, node1, node5, node3, node6, node4]
root = solve(tree)
print(treeprint(root, None))
입력
node6 = Node(65) node5 = Node(56) node4 = Node(42, [node5, node6]) node3 = Node(32) node2 = Node(27) node1 = Node(14, [node2, node3, node4]) tree = [node2, node1, node5, node3, node6, node4]
출력
[14, 27, 32, 42, 56, 65]
동작 원리 정리
이 알고리즘의 시간 복잡도는 O(N)입니다. 여기서 N은 트리의 전체 노드 수입니다. 모든 노드와 간선을 한 번씩만 순회하면 되기 때문입니다. 공간 복잡도 역시 진입 차수를 저장하는 맵 때문에 O(N)입니다.
핵심 아이디어를 요약하면 다음과 같습니다. 트리에서 루트를 제외한 모든 노드는 반드시 하나의 부모를 가지므로 진입 차수가 1 이상입니다. 따라서 진입 차수가 0인 노드, 즉 누구에게도 자식으로 지목되지 않은 노드가 바로 루트 노드가 됩니다. 이 성질만 이해하면 배열에 담긴 순서와 상관없이 루트를 손쉽게 찾을 수 있습니다.