C++로 N-진 트리(N-ary Tree) 직렬화와 역직렬화 구현하기

문제 개요

N-진 트리(N-ary Tree)가 하나 주어졌을 때, 이 트리를 직렬화(serialize)하고 역직렬화(deserialize)해야 한다고 가정해 봅시다.

직렬화(Serialization)란 데이터 구조나 객체를 일련의 비트 형태로 변환하여 파일이나 메모리 버퍼에 저장할 수 있게 하는 과정입니다. 저장된 데이터는 이후 동일한 환경 또는 다른 컴퓨터 환경에서 원래 상태 그대로 복원할 수 있습니다.

N-진 트리(N-ary Tree)는 루트(root)를 가지며, 각 노드가 최대 N개까지만 자식 노드를 가질 수 있는 트리 구조를 의미합니다.

예를 들어 다음과 같은 트리가 입력으로 주어졌다고 가정해 보겠습니다.

C++로 N-진 트리(N-ary Tree) 직렬화와 역직렬화 구현하기

이 경우 출력 결과는 다음과 같습니다.

Serialize(직렬화 결과): 1 #3 2 4 #5 6 #####
Deserialized Tree(역직렬화된 트리): 1[3[5, 6], 2, 4]

해결 접근 방법

이 문제는 너비 우선 탐색(BFS) 방식을 활용하여 해결할 수 있습니다. 전체 알고리즘은 세 가지 핵심 함수로 구성됩니다.

1. createVector() 함수 — 문자열 파싱

직렬화된 문자열을 파싱하여 2차원 정수 벡터로 변환하는 보조 함수입니다.

2차원 배열 ret과 임시 배열 tempv, 임시 문자열 temp를 선언합니다.
문자열 s를 처음부터 끝까지 순회하면서 다음 규칙에 따라 처리합니다.
- 현재 문자가 공백도 아니고 #도 아니라면 → temp에 해당 문자를 누적합니다.
- 현재 문자가 공백이라면 → 지금까지 누적한 temp를 정수로 변환하여 tempv에 추가하고, temp를 초기화합니다.
- 현재 문자가 #이라면 → tempv를 ret에 저장한 뒤, temp와 tempv를 모두 초기화합니다.
순회가 끝난 후, ret의 마지막 요소가 빈 벡터인 동안 계속 제거합니다(불필요한 빈 레벨 제거).
최종적으로 ret을 반환합니다.

2. serialize() 함수 — 트리를 문자열로 변환

결과 문자열 ret을 빈 문자열로 초기화하고, 루트가 null이면 그대로 반환합니다.
큐 q를 생성하고 루트 노드를 삽입한 뒤, 루트의 값과 공백, 그리고 #을 ret에 추가합니다.
큐가 빌 때까지 다음을 반복합니다.
- 큐의 맨 앞 노드를 꺼내 curr에 저장합니다.
- curr의 자식들을 순서대로 확인하며, 자식이 존재하면 그 값을 ret에 추가하고 해당 자식을 큐에 삽입합니다. 각 자식 처리 후에는 공백을 추가합니다.
- 한 노드의 자식 처리가 끝나면 #을 추가하여 레벨의 경계를 표시합니다.
완성된 문자열 ret을 반환합니다.

3. deserialize() 함수 — 문자열을 트리로 복원

입력 문자열 data의 길이가 0이면 null을 반환합니다.
createVector()를 호출하여 2차원 벡터 v를 얻습니다.
v[0][0] 값을 가진 새 노드를 루트로 생성하고, 큐에 삽입합니다. 인덱스 i는 1부터 시작합니다.
큐가 비어 있지 않고 i가 v의 크기보다 작은 동안 다음을 반복합니다.
- 큐에서 노드를 꺼내 curr에 저장합니다.
- v[i]의 각 값을 순회하며 새 노드를 생성하고, curr의 자식 목록에 추가한 뒤 큐에도 삽입합니다.
- i를 1 증가시킵니다.
복원된 트리의 루트 ret을 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) {
       val = _val;
    }
    Node(int _val, vector<Node*> _children) {
       val = _val;
       children = _children;
    }
};
string n_ary_to_str(Node *root){
    string ret = "";
    if(root){
       ret = ret + to_string(root->val);
       if(root->children.size() > 0){
          ret += "[";
          for(Node* child : root->children){
             ret += n_ary_to_str(child) + ", ";
          }
          ret += "]";
       }
    }
    return ret;
}
class Codec {
public:
    vector<vector<int>>createVector(string s) {
       vector<vector<int>> ret;
       vector<int> tempv;
       string temp = "";
       for (int i = 0; i < s.size(); i++) {
          if (s[i] != ' ' && s[i] != '#') {
             temp += s[i];
          }
          else if (s[i] == ' ') {
             tempv.push_back(stoi(temp));
             temp = "";
          }
          else if (s[i] == '#') {
             ret.push_back(tempv);
             temp = "";
             tempv.clear();
          }
       }
       while (!ret.empty() && ret.back().size() == 0)
       ret.pop_back();
       return ret;
    }
    string serialize(Node *root) {
       string ret = "";
       if (!root)
          return ret;
       queue<Node *> q;
       q.push(root);
       ret += to_string(root->val);
       ret += " ";
       ret += "#";
       while (!q.empty()) {
          Node *curr = q.front();
          q.pop();
          for (int i = 0; i < curr->children.size(); i++) {
             if (curr->children[i]) {
                ret += to_string(curr->children[i]->val);
                q.push(curr->children[i]);
             }
             ret += " ";
          }
          ret += "#";
       }
       return ret;
    }
    Node *deserialize(string data) {
       Node *ret;
       if (data.size() == 0)
          return NULL;
       vector<vector<int>> v = createVector(data);
       ret = new Node(v[0][0]);
       queue<Node *> q;
       q.push(ret);
       int i = 1;
       while (!q.empty() && i < v.size()) {
          Node *curr = q.front();
          q.pop();
          for (int j = 0; j < v[i].size(); j++) {
             int node = v[i][j];
             Node *temp = new Node(node);
             curr->children.push_back(temp);
             q.push(temp);
          }
          i++;
       }
       return ret;
    }
};
main() {
    Codec ob;
    Node n5(5), n6(6);
    Node n3(3); n3.children.push_back(&n5); n3.children.push_back(&n6);
    Node n2(2), n4(4);
    Node n1(1); n1.children.push_back(&n3); n1.children.push_back(&n2);
    n1.children.push_back(&n4);
    cout << "Given Tree: " << n_ary_to_str(&n1) << endl;
    string ser = ob.serialize(&n1);
    cout << "Serialize: " << ser << endl;
    Node *deser = ob.deserialize(ser);
    cout << "Deserialized Tree: " << n_ary_to_str(deser);
}

입력

Node n5(5), n6(6);
Node n3(3); n3.children.push_back(&n5); n3.children.push_back(&n6);
Node n2(2), n4(4);
Node n1(1); n1.children.push_back(&n3); n1.children.push_back(&n2);
n1.children.push_back(&n4);

출력

Given Tree: 1[3[5, 6], 2, 4]
Serialize: 1 #3 2 4 #5 6 #####
Deserialized Tree: 1[3[5, 6], 2, 4]

마무리

이 알고리즘은 BFS(레벨 순서 순회)를 기반으로 하므로, 각 트리 레벨을 # 구분자로 명확하게 구분할 수 있다는 점이 핵심입니다. 이러한 구분자 기반 직렬화 방식은 트리의 구조 정보를 손실 없이 문자열로 보존하며, 역직렬화 시에도 동일한 순서로 노드를 재구성할 수 있게 해줍니다. 시간 복잡도는 트리의 노드 수를 V라고 할 때 직렬화와 역직렬화 모두 O(V)이며, 공간 복잡도 역시 큐 사용으로 인해 O(V)입니다.