c++) 두니발 박사의 탈옥 (dp)

문제 : algospot.com :: NUMB3RS

algospot.com :: NUMB3RS

두니발 박사는 처음에 교도소에 위치해있고, 하루마다 연결된 마을로 이동합니다.

주어진 일수가 지난 후 각 마을에 있을 확률을 구하는 문제입니다.

 

풀이과정

완전탐색을 이용해서 문제를 해결할 수 있지만, 최대 마을의 수가 50 이고 최대 일수는 100일이기 때문에

최악의 경우 50^100 가지를 탐색해야 하기 때문에 메모이제이션이 필요합니다.

 

현재 위치 now과 지난 일수 day를 사용한 searching 재귀함수를 생각해보면,

searching(now, day) 는

now위치에 있으며, day만큼 지났을 때 마지막 일수에 도달했을 시 주어진 마을에 있을 확률

이라고 생각해볼 수 있으며, 점화식을 세워보면

이런 식으로 세울 수 있으며, 확률을 구하기 위해 counts 배열에는

now와 인접한 마을의 개수를 담고 있습니다.

 

추가적으로 기저사례에 day가 주어진 일수에 도달했을 때 주어진 마을에 도착했는지를 검사하면 됩니다.

 

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;
int C,N,D,P,T,Q;

int village[51][51], counts[51];
// cache[마을 번호][날짜]
double cache[51][101];

/* 완전탐색
double allSearch(vector < int > &path) {
    // 날짜에 도달했다면
    if(path.size() == D+1) {
        // 도착을 제대로 한 경우
        if(path.back() == Q) {
            double result = 1.0;
            for(int i=0; i+1<path.size(); i++) {
                int next = counts[path[i]];
                result /= next;
            }
            return result;
        }
        else return 0;
    }
    double ret = 0;
    for(int i=0; i<N; i++) {
        // 마지막 지점과 연결되어있다면
        if(village[path.back()][i]) {
            path.push_back(i);
            ret += allSearch(path);
            path.pop_back();
        }
    }
    return ret;
}
*/

// 현재 위치에 있고 해당 날짜일 때 마지막날 도달 시 확률 반환
double searching(int now, int day) {
    // 기저사례 : 마지막 날 도달 시
    if(day == D) {
        if(now == Q) return 1;
        else return 0;
    }
    double &ret = cache[now][day];
    if(ret != -1.0) return ret;

    ret = 0.0;
    for(int i=0; i<N; i++) {
        if(village[now][i])
            ret += (searching(i,day+1)/counts[now]);
    }
    return ret;
}

int main()
{
    scanf("%d",&C);
    for(int c=0; c<C; c++) {
        scanf("%d %d %d",&N,&D,&P);
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                scanf("%d",&village[i][j]);
                if(village[i][j]) counts[i]++;
            }
        }
        scanf("%d",&T);
        for(int i=0; i<T; i++) {
            for(int i=0; i<51; i++)
                for(int j=0; j<101; j++)
                    cache[i][j] = -1.0;
            scanf("%d",&Q);
            printf("%lf ",searching(P,0));
        }
        printf("\n");
        memset(counts,0,sizeof(counts));
    }
}