두니발 박사의 탈옥 (CODE: NUMB3RS)

링크: https://www.algospot.com/judge/problem/read/NUMB3RS

문제 두니발 박사의 탈옥이다. 두니발 박사가 감옥에서 탈출했다. 두니발 박사는 연결되어 있는 마을을 통해 이동하는데 이때 규칙을 따른다.

• 두니발 박사는 검문을 피해 산길로만 이동한다.
• 두니발 박사는 교도소를 탈출한 당일, 교도소와 인접한 마을 하나로 도망쳐 은신한다.
• 두니발 박사는 수색을 피하기 위해 매일 인접한 마을로 움직여 은신한다.

이 때 d일 이후에 두니발 박사가 각 마을에 있을 확률을 계산하는 프로그램을 작성하라.

입력

입력 첫 줄에는 테스트 케이스 C(1<=C<=50)이 주어진다. 그 후 각 줄에 지도에 포함된 마을의 수 N(2<=N<=50)과 탈출 후 지금까지 지난 일수 D(1<=D<=100) 교도소가 있는 마을의 번호 P(0<=P<N)이 주어진다. 그 후에 행렬 A가 주어진다. 행렬은 각 마을을 잇는 산길이 있음을 의미한다. 그 다음 줄에 마을의 수 T(0<=T<N)이 주어지고, 다음 줄에 T개의 정수로 확률이 계산할 마을의 번호 Q가 주어진다.

예제 입력

2
5 2 0
0 1 1 1 0
1 0 0 0 1
1 0 0 0 0
1 0 0 0 0
0 1 0 0 0
3
0 2 4
8 2 3
0 1 1 1 0 0 0 0
1 0 0 1 0 0 0 0
1 0 0 1 0 0 0 0
1 1 1 0 1 1 0 0
0 0 0 1 0 0 1 1
0 0 0 1 0 0 0 1
0 0 0 0 1 0 0 0
0 0 0 0 1 1 0 0
4
3 1 2 6

코드

#include <cstdio>
#include <cstring>

int n,d,p,Q;//n은 마을의 수, d는 일수
//p는 교도소가 있는 마을의 번호, Q: 확률을 알아내기 위한 마을 번호
int arr[51][51], deg[51];
double cache[51][101];

double search(int here, int days){
    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(arr[here][there])
            ret += search(there, days - 1) / deg[there];
    return ret;
}
// here에 올 확률은 here과 연결되어 있는 (there에 올 확률) *
// (there이 연결되어 있는 마을의 수)의 합이다.

int main(){
    int C; // c는 test case
    int T;// T에 관한 마을의 수
    double ans;
    scanf("%d", &C);
    while(C--){
        memset(cache, -1, sizeof(cache));
        memset(deg, 0, sizeof(deg));
        scanf("%d %d %d", &n, &d, &p);
        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                scanf("%d", &arr[i][j]);
                deg[i] += arr[i][j];
            }
        }
        scanf("%d", &T);
        for(int i = 0; i<T; i++){
            scanf("%d", &Q);
            ans = search(Q, d);
            printf("%.8f ", ans);
        }
        printf("\n");
    }
    return 0;
}

• 마르코프 연쇄: 마르코프 연쇄는 시간에 따른 계의 상태의 변화를 나타낸다. 마르코프 성질은 과거와 현재 상태가 주어졌을 때의 미래 상태의 조건부 확률 분포가 과거 상태와는 독립적으로 현재 상태에 의해서만 결정된다는 것을 뜻한다.

특징

• 유한개의 상태가 있음
• 매시간마다 상태가 변경
• 어떤 상태 a에서 다른 상태 b로 옮겨갈 확률은 현재 상태 a에만 좌우, a 이전에 어느 상태에 있었는지 현재 시간은 얼마인지에 영향을 받지 않음.