[algospot] 두니발 박사의 탈옥 (c++)

출처 : algospot.com :: NUMB3RS

algospot.com :: NUMB3RS

풀이 방법

dp 문제이다.

마을의 정보를 입력받으면서 deg를 계산해주어 각 마을이 연결된 통로를 계산해준다.

기저 조건으로 days == 0 일 때 지금 위치가 목표지점이면 1.0을 리턴 아니면 0.0을 리턴하여 그 값에다 deg를 나누어 주어 확률을 계산하다.

기저 사례가 아닌 경우는 연결된 마을로 이동하는 재귀 호출을 하여 그 값에 deg를 나누어 주어서 확률을 계산한다.

 

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

double cache[51][101];
int connected[51][51];
int deg[51];
int n,d,p,q;

double search(int here, int days){
	//기저 조건 끝났는데 그 마을에 도착했으면 1리턴 아니면 0 리턴
    if(days == 0) return (here == p ? 1.0 : 0.0);
    
    double &ret = cache[here][days];
    if(ret > -0.5) return ret;
    
    ret = 0.0;
    for(int there=0;there<n;++there)
        if(connected[here][there])
            ret += search(there, days-1) / deg[there];
    return ret;
}

int main(){    
    int c;
    cin >> c;
    while(c--){
        memset(cache, -1, sizeof(cache));
        memset(deg, 0, sizeof(deg));

        cin >> n >> d >> p;
        for(int i = 0;i < n; i++){
            for(int j = 0;j < n; j++){
                cin >> connected[i][j];                
                deg[i] += connected[i][j];
            }
        }

        cin >> q;
        while(q--){
            int a;
            cin >> a;
            cout.precision(8);
            cout << search(a, d) << " ";
        }
        cout << endl;
    }
}