Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 N-ary 트리 레벨 순회(Level Order Traversal)

N-ary 트리(N-ary Tree)는 각 노드가 최대 n개의 자식 노드를 가질 수 있는 트리 구조입니다. 이번 글에서는 이러한 N-ary 트리의 레벨 순회(Level Order Traversal), 즉 너비 우선 탐색(BFS) 방식으로 노드 값을 층별로 출력하는 방법을 C++ 코드와 함께 자세히 알아보겠습니다.

문제 정의

N-ary 트리가 주어졌을 때, 각 노드의 값을 레벨(깊이) 단위로 묶어 반환하는 것이 목표입니다. 입력은 레벨 순회 형태로 직렬화되며, 각 그룹의 자식 노드들은 null 값으로 구분됩니다.

예를 들어 다음과 같은 트리는 [1,null,3,2,4,null,5,6]으로 표현할 수 있습니다.

  • 루트 노드: 1
  • 1의 자식들: 3, 2, 4
  • 3의 자식들: 5, 6

이때 기대되는 출력 결과는 다음과 같습니다.

[[1], [3, 2, 4], [5, 6]]

해결 접근 방법

레벨 순회는 큐(Queue)를 활용하는 BFS 알고리즘으로 해결할 수 있습니다. 핵심 아이디어는 큐에 들어있는 노드 수를 미리 파악하여, 같은 레벨의 노드들을 한 번에 처리하는 것입니다.

알고리즘 단계

  1. 결과를 저장할 2차원 벡터 ans를 생성합니다.
  2. 루트가 null이면 빈 결과를 반환합니다.
  3. 큐 q를 만들고 루트 노드를 삽입합니다.
  4. 큐가 비어 있지 않은 동안 반복합니다.
    1. 현재 큐의 크기를 size에 저장합니다. (현재 레벨의 노드 수)
    2. 현재 레벨의 값을 담을 배열 temp를 생성합니다.
    3. size가 0이 될 때까지 반복합니다.
      1. 큐의 맨 앞 요소를 curr로 가져옵니다.
      2. curr의 값을 temp에 삽입합니다.
      3. 큐에서 해당 요소를 제거합니다.
      4. curr의 모든 자식 노드를 큐에 삽입합니다.
    4. temp를 ans에 추가합니다.
  5. ans를 반환합니다.

C++ 구현 코드

아래는 위 알고리즘을 C++로 구현한 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto>> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class Node {
   public:
   int val;
   vector<Node*> children;
   Node() {}
   Node(int _val) {
      val = _val;
   }
   Node(int _val, vector<Node*> _children) {
      val = _val;
      children = _children;
   }
};
class Solution {
   public:
   vector<vector<int>> levelOrder(Node* root) {
      vector<vector<int>> ans;
      if(!root)return ans;
      queue<Node*> q;
      q.push(root);
      while(!q.empty()){
         int sz = q.size();
         vector<int> temp;
         while(sz--){
            Node* curr = q.front();
            temp.push_back(curr->val);
            q.pop();
            for(int i = 0; i < curr->children.size(); i++){
               q.push(curr->children[i]);
            }
         }
         ans.push_back(temp);
      }
      return ans;
   }
};
main(){
   Node *root = new Node(1);
   Node *left_ch = new Node(3), *mid_ch = new Node(2), *right_ch = new Node(4);
   left_ch->children.push_back(new Node(5));
   left_ch->children.push_back(new Node(6));
   root->children.push_back(left_ch);
   root->children.push_back(mid_ch);
   root->children.push_back(right_ch);
   Solution ob;
   print_vector(ob.levelOrder(root));
}

실행 결과 확인

입력

[1,null,3,2,4,null,5,6]

출력

[[1],[3, 2, 4],[5, 6]]

시간 및 공간 복잡도 분석

  • 시간 복잡도: O(n) — 모든 노드를 정확히 한 번씩 방문합니다.
  • 공간 복잡도: O(n) — 큐에는 최악의 경우 트리의 가장 넓은 레벨에 있는 노드들이 모두 저장될 수 있습니다.

마무리

N-ary 트리의 레벨 순회는 이진 트리의 BFS와 동일한 원리를 사용하지만, 자식 노드가 두 개로 제한되지 않고 벡터로 관리된다는 점이 차이입니다. 큐의 크기를 루프 시작 시점에 저장해두면 레벨별로 값을 깔끔하게 그룹화할 수 있다는 점을 기억하시기 바랍니다. 이 패턴은 그래프 탐색, 최단 경로 문제 등 다양한 알고리즘 문제에서도 응용되므로 확실하게 익혀두는 것이 좋습니다.