[c언어/c++] 두니발 박사의 탈옥 NUMB3RS 동적계획법, 확률

위험한 살인마 두니발 박사가 감옥에서 탈출했습니다. 수배지를 붙이고 군경이 24시간 그를 추적하고 있지만 용의주도한 두니발 박사는 쉽사리 잡히지 않았습니다. d일이 지난 후에야 경찰은 프로그래밍의 천재인 찰리 교수)를 찾아왔습니다. 찰리 교수는 두니발 박사가 감옥에 남겨둔 노트를 분석해 다음과 같은 가설을 세웠습니다.

두니발 박사는 검문을 피해 산길로만 이동한다.

두니발 박사는 교도소를 탈출한 당일, 교도소와 인접한 마을 하나로 도망쳐 은신한다.

두니발 박사는 수색을 피하기 위해 그 후 매일 인접한 마을로 움직여 은신한다.

이 가설을 검증하기 위해 교도소로부터 산길로 연결된 n 개 마을들의 지도를 위 그림과 같이 구했습니다. 두니발 박사가 이 가설에 맞춰 행동하고, 움직일 수 있는 마을이 여러 개 있을 경우 그 중의 하나를 임의로 선택한다고 합시다. d 일 후에 두니발 교수가 각 마을에 있을 확률을 계산하는 프로그램을 작성하세요.

예를 들어 위 지도에서 3번 마을에 교도소가 있다고 합시다. 탈옥 직후 두니발 교수는 0번, 1번, 2번, 4번, 5번 중의 한 도시를 임의로 골라 도망칩니다. 따라서 1일 후에 두니발 교수가 0번 마을에 숨어 있을 확률은 1/5이고, 2일 후에 1번 마을에 숨어 있을 확률은 1/15입니다.

전체 링크 - https://algospot.com/judge/problem/read/NUMB3RS

#include<stdio.h>

#include<memory.h>

#include<algorithm>

using namespace std;

int n,d,p,t;

int q[101];

int A[101][101];

int total[101];

double cache[101][101];

double esc(int,int,int);

int main(){

int loop;

scanf(" %d",&loop);

while(loop-- > 0){

memset(A,0,sizeof(A));

memset(q,0,sizeof(q));

memset(total,0,sizeof(total));

scanf(" %d %d %d",&n,&d,&p);

for(int i = 0 ; i < n ; i++)

for(int j = 0 ; j < n ; j++)

scanf(" %d",&A[i][j]);

scanf(" %d",&t);

for(int i = 0 ; i < n ; i++)

for(int j = 0 ; j < n ; j++ )

total[i] = total[i] + A[i][j];

for(int i = 0 ; i < t ; i++) scanf(" %d",&q[i]);

for(int i = 0 ; i < t ; i++){

memset(cache,-1,sizeof(cache));

printf("%0.8lf ",esc(p,0,q[i]));

}

printf("\n");

}//end of while

return 0;

}//end of main

double esc(int here,int days,int quit){

if(days == d) return (here == quit ? 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(A[here][there])

ret+=esc(there,days+1,quit)/total[here];

return ret;

}