C++로 N-ary 트리 순회 방법의 총 개수 구하기

N-ary(다진) 트리가 주어졌을 때, 이 트리를 순회할 수 있는 모든 방법의 수를 구하는 문제입니다. 아래 예시 트리를 살펴보겠습니다.

위 트리에 대한 정답은 192가 됩니다.

이 문제를 해결하려면 조합론(combinatorics)에 대한 기본적인 지식이 필요합니다. 핵심 아이디어는 각 노드의 자식들에 대해 가능한 모든 순열 조합을 곱해 나가는 것입니다.

문제 해결 접근 방식

이 접근법에서는 레벨 순서 순회(level order traversal)를 수행하면서 각 노드가 가진 자식의 개수를 확인하고, 그 개수의 팩토리얼(factorial) 값을 정답에 계속 곱해주면 됩니다.

왜냐하면 어떤 노드의 자식이 k개라면, 그 자식들을 방문하는 순서의 경우의 수는 k!이기 때문입니다. 따라서 모든 노드에 대해 자식 수의 팩토리얼을 곱하면 전체 순회 방법의 수가 됩니다.

C++ 코드 예제

#include<bits/stdc++.h>
using namespace std;
struct Node{ // 노드 구조체 정의
    char key;
    vector<Node *> child;
};
Node *createNode(int key){ // 새 노드를 생성하는 함수
    Node *temp = new Node;
    temp->key = key;
    return temp;
}
long long fact(int n){ // 팩토리얼 계산 함수
    if(n <= 1)
        return 1;
    return n * fact(n-1);
}
int main(){
    Node *root = createNode('A');
    (root->child).push_back(createNode('B'));
    (root->child).push_back(createNode('F'));
    (root->child).push_back(createNode('D'));
    (root->child).push_back(createNode('E'));
    (root->child[2]->child).push_back(createNode('K'));
    (root->child[1]->child).push_back(createNode('J'));
    (root->child[3]->child).push_back(createNode('G'));
    (root->child[0]->child).push_back(createNode('C'));
    (root->child[2]->child).push_back(createNode('H'));
    (root->child[1]->child).push_back(createNode('I'));
    (root->child[2]->child[0]->child).push_back(createNode('N'));
    (root->child[2]->child[0]->child).push_back(createNode('M'));
    (root->child[1]->child[1]->child).push_back(createNode('L'));
    queue<Node*> q;
    q.push(root);
    long long ans = 1;
    while(!q.empty()){
        auto z = q.front();
        q.pop();
        ans *= fact(z -> child.size());
        cout << z->child.size() << " ";
        for(auto x : z -> child)
           q.push(x);
   }
   cout << ans << "\n";
   return 0;
}

실행 결과

4 1 2 2 1 0 0 1 2 0 0 0 0 0 192

코드 설명

위 코드에서는 BFS(너비 우선 탐색), 즉 레벨 순서 순회를 적용하여 각 노드가 가지고 있는 자식의 개수를 확인합니다. 그런 다음 그 개수의 팩토리얼 값을 정답 변수에 곱해 나갑니다.

출력 결과를 보면 먼저 각 노드의 자식 수가 순서대로 출력되고, 마지막에 전체 순회 방법의 수인 192가 출력됩니다. 예를 들어 루트 노드 A는 자식이 4개이므로 4! = 24가 되고, 이후 각 노드의 경우의 수가 누적으로 곱해져 최종 결과가 만들어집니다.

마무리

이 글에서는 조합론과 BFS(레벨 순서 순회)를 활용하여 N-ary 트리를 순회하는 방법의 총 개수를 구하는 방법을 알아보았습니다. 또한 이 문제를 해결하는 완전한 C++ 프로그램도 함께 살펴보았습니다.

동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다. 이 튜토리얼이 여러분의 학습에 도움이 되기를 바랍니다.