171022_NUMB3RS_두니발 박사의 탈옥

#include <iostream>
using namespace std;

int main()
{
  int c; //# of case
  cin >> c;
  
  for(int i=0; i < c; i++)
  {
	int n,d,p; // n: # of ville, d : day, p : starting point
	cin >> n >> d >> p;
	int np;
	double sum=0;
	bool map[50][50]={0};
	double prob[50][50]={0}; 
	//prob[before][after] moving befor->after probability
	double dp[101][50]={0};
	//dp[day][where is he]
	
	for(int r=0; r<n; r++)
	{
	  int cnt=0;
	  
	  for(int c=0; c<n; c++)
	  {
		cin >> map[r][c];
		if(map[r][c]) cnt++;
	  }
	  
	  for(int c=0; c<n; c++) //a마을->b마을로 가는 확률 prob[a][b]
		if(map[r][c]) 
		   prob[r][c]=(double)1/(double)cnt;
	}
	dp[0][p]=1;
	
	for(int day=1; day<=d; day++)
	{
	  for(int v=0; v<n; v++)
	  {
		for(int j=0; j<n; j++)
		  sum=sum+dp[day-1][j]*prob[j][v];
		dp[day][v]=sum;
		sum =0;
	  }
	}
	
	cin >> np;
	for(int i=0; i<np; i++)
	{
	  int x;
	  cin >> x; 
	  cout << fixed;
	  cout.precision(8);
	  cout << dp[d][x] << " " ;
	}
	cout << endl;
  }
	
}

1) prob[a][b] 로 각각 0->0, 0->1, ... , 0->n, 1->0, ... ,n->n 확률 구해줌

2) 점화식 : 

dp[day][v] = dp[day-1][0]*prob[0][v]+dp[day-1][1]*prob[1][v] + dp[day-1][2]*prob[2][v] + ... + dp[day-1][n]*prob[n][v]

 : 

(day에서 v마을에 있을 확률)

= (하루전날에 0마을에 있을 확률)*(0마을에서 v마을로 갈 확률) 

 +(하루전날에 1마을에 있을 확률)*(1마을에서 v마을로 갈 확률)

 +(하루전날에 2마을에 있을 확률)*(2마을에서 v마을로 갈 확률) 

 +...

 +(하루전날에 n마을에 있을 확률)*(n마을에서 v마을로 갈 확률)