ตำแหน่งของกบหลังจาก T วินาทีใน C++

คำอธิบายโจทย์

สมมติว่าเรามีต้นไม้แบบไม่มีทิศทาง (undirected tree) ที่ประกอบด้วย n จุดยอด (vertices) หมายเลข 1 ถึง n กบเริ่มกระโดดจากจุดยอด 1 กบสามารถกระโดดจากจุดยอดปัจจุบันไปยังจุดยอดที่ยังไม่ได้เยี่ยมชมและติดกันได้ในเวลา 1 วินาที กบไม่สามารถกระโดดกลับไปยังจุดยอดที่เคยเยี่ยมชมแล้ว หากมีหลายทางเลือก กบจะเลือกสุ่มอย่างเท่าเทียม หากไม่มีที่จะกระโดดต่อ กบจะอยู่ที่เดิมตลอดไป

ต้นไม้ถูกกำหนดโดยอาร์เรย์ของเส้นเชื่อม (edges) เราต้องหาความน่าจะเป็นที่หลังจาก t วินาที กบจะอยู่ที่จุดยอด target

ตัวอย่าง

n = 7, t = 2, target = 4 และต้นไม้มีโครงสร้างดังนี้:

ผลลัพธ์คือ 0.1666 เนื่องจากจากจุดยอด 1 กบกระโดดไปจุดยอด 2 ด้วยความน่าจะเป็น 1/3 ในวินาทีที่ 1 แล้วกระโดดไปจุดยอด 4 ด้วยความน่าจะเป็น 1/2 ในวินาทีที่ 2 ดังนั้นความน่าจะเป็นรวม = 1/3 × 1/2 = 1/6 ≈ 0.1667

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

1. สร้างกราฟจาก edges โดยใช้ adjacency list
2. ใช้ DFS เพื่อหาเส้นทางจาก target กลับไปยังราก (จุดยอด 1) พร้อมบันทึกเวลา (tt) และเส้นทางใน stack
3. คำนวณความน่าจะเป็นโดยการคูณ 1/(จำนวนทางเลือกที่แต่ละจุดยอดบนเส้นทาง) โดยจุดยอด 1 ใช้ degree ปกติ ส่วนจุดยอดอื่นใช้ degree - 1 (เพราะมาจาก parent)
4. ตรวจสอบเงื่อนไข:
   • ถ้า tt > t → คืนค่า 0 (กบยังไม่ถึง target)
   • ถ้า tt == t → คืนค่าความน่าจะเป็นที่คำนวณได้
   • ถ้า tt < t และ target == 1 และมีลูก → คืนค่า 0 (กบจะกระโดดต่อ)
   • ถ้า tt < t และ target มีลูกมากกว่า 1 → คืนค่า 0 (กบจะกระโดดต่อ)
   • อื่นๆ → คืนค่าความน่าจะเป็น (กบติดที่ target เพราะไม่มีที่กระโดด)

การทำงานของโค้ด

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    double ret = 1;
    bool ok = false;
    set<int> visited;
    int tt;

    bool dfs(int node, int start, vector<int> g[], int time, int t, stack<int>& st) {
        if (visited.count(node)) return false;
        visited.insert(node);
        if (node == 1) {
            tt = time;
            ok = true;
            return true;
        }
        for (int i = 0; i < g[node].size(); i++) {
            st.push(g[node][i]);
            if (dfs(g[node][i], start, g, time + 1, t, st)) return true;
            st.pop();
        }
        return false;
    }

    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        ret = 1;
        ok = false;
        vector<int> graph[n + 1];
        for (int i = 0; i < edges.size(); i++) {
            graph[edges[i][0]].push_back(edges[i][1]);
            graph[edges[i][1]].push_back(edges[i][0]);
        }
        stack<int> st;
        dfs(target, target, graph, 0, t, st);
        while (!st.empty()) {
            int node = st.top();
            double sz = graph[node].size();
            if (node != 1) sz--;
            ret *= (1.0 / sz);
            st.pop();
        }
        if (tt > t) return 0;
        if (tt == t) return ret;
        if (tt < t && target == 1 && graph[target].size() >= 1) return 0;
        return (tt < t && graph[target].size() > 1) ? 0 : ret;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}};
    cout << fixed << setprecision(6) << ob.frogPosition(7, v, 2, 4);
    return 0;
}

อินพุต

7, {{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}}, 2, 4

เอาต์พุต

0.166667