C++를 사용하여 N-ary 트리를 순회하는 방법의 수 찾기

N-ary 트리가 주어지고 우리는 이 트리를 순회하는 총 방법 수를 찾는 임무를 받았습니다. 예를 들면 -

위 트리의 경우 출력은 192가 됩니다.

이 문제를 풀기 위해서는 조합론에 대한 지식이 필요합니다. 이제 이 문제에서 모든 경로에 대해 가능한 모든 조합을 확인하기만 하면 답이 나옵니다.

해결책을 찾기 위한 접근 방식

이 접근 방식에서 우리는 단순히 레벨 순서 순회를 수행하고 각 노드가 가진 자식 수를 확인한 다음 답에 팩토리얼을 곱하면 됩니다.

예시

위 접근 방식에 대한 C++ 코드

#include<bits/stdc++.h>
using namespace std;
struct Node{ // structure of our node
    char key;
    vector<Node *> child;
};
Node *createNode(int key){ // function to initialize a new node
    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(Breadth-First Search) 또는 레벨 순서 순회를 적용하고 각 노드가 갖는 자식 수를 확인합니다. 그런 다음 해당 숫자의 계승을 답에 곱합니다.

결론

이 튜토리얼은 N-ary 트리 조합을 탐색하고 BFS를 적용하는 몇 가지 방법을 찾습니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 우리가 해결한 완전한 접근 방식을 배웠습니다.

C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 튜토리얼이 도움이 되기를 바랍니다.