[동적계획법] 13. 두니발 박사의 탈옥 - 오답

 

내가 쓴 코드(오답) - 왜 틀렸는지 모름

/**
 * @name    8.16.두니발 박사의 탈옥
 * @ID      NUMB3RS
 * @date    2019-08-13
 * @author  Sunmon
 */
 
//FIXME: 오답!!!
 
 
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
int connected[50][50];  //connected[a][b]; a마을과 b마을이 연결되어있는지 저장
double cache[50][50];   //cache[town][day] ; day일에 town에 있을 확률
int sumConnect[50];     //sumConnect[a]; a마을에 연결된 마을 수
int N, DAY, PRISON;
 
 
//day일 후 k번 마을에 박사가 있을 확률 리턴
double dunnibal(int town, int day)
{
    //base case
    if(day == 1) return (double)connected[town][PRISON] / sumConnect[PRISON] ;
 
    double& ret = cache[town][day];
    if(ret != -1) return ret;
 
    ret = 0;
 
    //하루 전에 i번째 마을에 있었을 확률을 역추적한다.
    for(int i= 0; i<N; i++)
    {
        if(connected[i][town] == 0) continue;
        ret += dunnibal(i, day-1) / sumConnect[i];
    }
 
    return ret;
}
 
 
int main()
{
    int C;
    cin >> C;
    while(C--)
    {
        memset(sumConnect,0,sizeof(sumConnect));
        fill_n(cache[0], 50*50, -1);
 
        cin >> N >> DAY >> PRISON ;
        for(int i = 0; i< N; i++)
        {
            for(int j = 0; j<N; j++)
            {
                cin >> connected[i][j];
                if(connected[i][j] == 1) sumConnect[i]++;
            }    
        }
        
        int t;
        cin >> t;
 
        while(t--)
        {
            int DESTINATION;
            cin >> DESTINATION;
            cout << fixed;
            cout.precision(8);
            cout << dunnibal(DESTINATION, DAY) << " ";
        }
       
        cout << endl;
 
        
 
    }
 
}