NUMB3RS (중하, p. 269)

어떻게 풀었나?#

이 이전 문제가 POLY인데, 책에는 NUMB3RS와 POLY모두 난이도 ‘중’으로 표시되어있다.

POLY 난이도가 거의 ‘상’에 가깝다면, NUMB3RS 난이도는 ‘하’에 가까운 것 같다.

난이도 ‘하’는 생각 자체가 필요 없는 문제들을 분류하였으므로, 이 문제는 ‘중하’로 결정했다.

정점 n에서 d일후 두니발 박사가 있을 확률을 f(n,d)로 나타내면,

$f(n,d) = \sum_{i=0}^{v[n].size()} (f(v[n][i],d-1)/v[v[n][i]].size())$

가 된다. (여기서 v[n]은 n의 인접 정점들만 저장한 vector를 의미한다.)

문제#

정답 코드#

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> v;
int CHKVAL;
int chk[51][101];
double dp[51][101];
int p;
double f(int x, int d) {
    if(d==0) {
        if(x==p) return 1;
        else return 0;
    }
    if(chk[x][d] == CHKVAL) return dp[x][d];
    chk[x][d] = CHKVAL;
    double & ret = dp[x][d];
    ret=0;
    for(int i=0; i<v[x].size(); i++) {
        int y = v[x][i];
        ret += f(y,d-1)/v[y].size();
    }
    return ret;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        int n,d,x; cin >> n >> d >> p;

        v.clear(); v.resize(n, vector<int>());

        CHKVAL++;
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                cin >> x;
                if(x) {
                    v[i].push_back(j);
                    v[j].push_back(i);
                }
            }
        }
        int t; cin >> t;
        for(int i=0; i<t; i++) {
            cin >> x;
            printf("%.8lf ", f(x,d));
        }
        puts("");
    }
    return 0;
}