C++ หาจำนวนวิธีเดินทาง (Traverse) ใน N-ary Tree

ได้รับ N-ary Tree มา เราถูกมอบหมายให้หาจำนวนวิธีเดินทาง (Traverse) ทั้งหมดของต้นไม้นี้ เช่น

สำหรับต้นไม้ข้างต้น ผลลัพธ์จะเป็น 192

สำหรับปัญหานี้ เราต้องมีความรู้เกี่ยวกับ Combinatorics (คณิตศาสตร์การจัดหมู่) ตอนนี้ในปัญหานี้ เราแค่ต้องตรวจสอบการจัดหมู่ที่เป็นไปได้ทั้งหมดสำหรับแต่ละเส้นทาง และนั่นจะให้คำตอบของเรา

วิธีการแก้ปัญหา

ในวิธีนี้ เราแค่ต้องทำ Level Order Traversal (BFS) และตรวจสอบจำนวนลูก (Children) ของแต่ละโหนด แล้วคูณ Factorial ของจำนวนนั้นเข้ากับคำตอบ

ตัวอย่าง

โค้ด 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 (Breadth-First Search) หรือ Level Order Traversal และตรวจสอบจำนวนลูกของแต่ละโหนด แล้วคูณ Factorial ของจำนวนนั้นเข้ากับคำตอบของเรา

สรุป

บทช่วยสอนนี้หาจำนวนวิธีเดินทาง N-ary Tree ด้วย Combinatorics และการประยุกต์ BFS เรายังได้เรียนรู้โปรแกรม C++ และวิธีแก้ปัญหา ซึ่งสามารถเขียนในภาษาอื่น เช่น C, Java, Python ได้ หวังว่าจะเป็นประโยชน์