[알고리즘 문제해결전략] NUMB3RS - 두니발 박사의 탈옥

[생각의 흐름]

1. 모든 경로(or 경우의수)를 완전 탐색 해본다.

2. 교도소의 인접한 마을(시작점)에서 탐색을 시작하는 경우 앞의 과정에서 계산한 확률 값이 필요하다. -> 까다로운 점

3. 시작점과 끝점을 뒤집어서 생각해 본다.

4. 끝점에서 시작해서 교됴소의 인접한 마을(시작점)으로 가는 경우만 구해서 확률을 계산한다.

 

 

/* https://www.algospot.com/judge/problem/read/NUMB3RS# */
#include <stdio.h>
#include <memory.h>

const int MAX_TOWN = 51;
const int MAX_DAY = 101;

int townMap[MAX_TOWN][MAX_TOWN];
double cache[MAX_DAY][MAX_TOWN];
int numOfConnectedTown[MAX_TOWN];

int n, d, p;

bool isTownConnected(int townA, int townB)
{
    return townMap[townA][townB] == 1 ? true : false;
}

double sol(int day, int townNum)
{
    if (day == 0)
    {
        // 기저사례 첫 날(0)에 마을 번호가 p인 경우
        return townNum == p ? 1.0 : 0.0;
    }

    double &ret = cache[day][townNum];

    // TIP : 실수는 정확히 비교(==) 하기가 어렵기 때문에 대소로 비교한다.
    if (ret > -0.5)
        return ret;
    ret = 0;

    for (int i = 0; i < n; i++)
    {
        if (isTownConnected(townNum, i))
        {
            ret += sol(day - 1, i) * (1.0 / (double)numOfConnectedTown[i]);
        }
    }

    return ret;
}

void reset()
{
    memset(numOfConnectedTown, 0, sizeof(numOfConnectedTown));
    for (int i = 0; i < MAX_DAY; i++)
    {
        for (int j = 0; j < MAX_TOWN; j++)
        {
            cache[i][j] = -1;
        }
    }
}

int main(void)
{
    int C;
    scanf("%d", &C);
    while (C--)
    {
        reset();

        scanf("%d %d %d", &n, &d, &p);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                scanf("%d", &townMap[i][j]);
                numOfConnectedTown[i] += townMap[i][j];
            }
        }

        for (int endTown = 0; endTown < n; endTown++)
        {
            // 마지막 마을을 시작점으로 두고 탐색을 시작한다.
            sol(d, endTown);
        }

        int q;
        scanf("%d", &q);
        while (q--)
        {
            int town;
            scanf("%d", &town);
            printf("%.8lf ", cache[d][town]);
        }
        printf("\n");
    }

    return 0;
}