Python으로 N-ary 트리 복사본 만들기 – BFS 기반 완전 복제 방법

루트 노드가 'root'로 주어지는 N-ary 트리(n-ary tree)가 있다고 가정해 보겠습니다. 우리가 해야 할 일은 이 트리 전체의 복사본을 만든 뒤, 원본 트리와 복사된 트리 두 개 모두에 대해 전위 순회(preorder traversal)를 수행하는 것입니다. 복사본 트리는 반드시 별도의 새로운 루트 노드를 사용하여 저장해야 합니다. 트리 노드의 구조는 다음과 같습니다.

Node:
    value : <integer>
    children : <array>

예를 들어 입력이 다음과 같다면

출력은 다음과 같습니다.

[14, 27, 32, 42, 56, 65]

트리가 정확하게 복사되었기 때문에 입력 트리와 출력 트리의 전위 순회 결과는 서로 동일합니다.

해결 접근 방법

이 문제는 너비 우선 탐색(BFS) 방식으로 큐(deque)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 원본 노드와 복사본 노드를 쌍(pair)으로 함께 관리하면서, 각 자식 노드를 순서대로 새롭게 생성해 연결하는 것입니다. 단계별로 살펴보겠습니다.

루트가 비어 있으면(None이면)
- 루트를 그대로 반환합니다.
head := 루트와 같은 값을 가지는 새 노드를 생성합니다.
q := root와 head를 포함하는 새로운 deque를 생성합니다.
q가 빌 때까지 다음 과정을 반복합니다.
- node := q에서 첫 번째 요소(원본 노드)를 꺼냅니다.
- cloned := q에서 첫 번째 요소(복사본 노드)를 꺼냅니다.
- node.children의 각 자식(chld)에 대해 다음을 수행합니다.
  - new_n := chld의 값을 가지는 새 노드를 생성합니다.
  - new_n을 cloned의 children 리스트에 추가합니다.
  - chld와 new_n을 q의 끝에 삽입합니다.
모든 처리가 끝나면 head를 반환합니다.

예제 코드 (Python)

아래 구현을 통해 더 자세히 이해해 보겠습니다.

from queue import deque
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(root):
    if not root:
        return root
    head = Node(root.val)
    q = deque([(root, head)])
    while q:
        node, cloned = q.popleft()
        for chld in node.children:
            new_n = Node(chld.val)
            cloned.children.append(new_n)
            q.append((chld,new_n))
    return head

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])
root = node1

copynode = solve(root)
print(treeprint(copynode, None))

입력

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

출력

[14, 27, 32, 42, 56, 65]

복잡도 분석

이 알고리즘의 시간 복잡도는 O(N)이며, 공간 복잡도 역시 O(N)입니다. 여기서 N은 트리의 전체 노드 수입니다. 각 노드를 정확히 한 번씩 방문하면서 복사하고, 큐에는 최대 트리의 한 레벨에 해당하는 노드만 저장되기 때문입니다.