[종만북 문제] 두니발 박사의 탈옥 (문제 ID : NUMB3RS, 난이도 : 중)

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다!

---

핵심 :

1. 흠.. 이 정돈가?

---

[종만북 문제] 두니발 박사의 탈옥 (문제 ID : NUMB3RS, 난이도 : 중)

여기까지 왔으면, 이제 DP 문제는 패턴이 학습되었을 것이다. 

그냥... 아래처럼 풀면 된달까요(웃음).

#include <iostream>
#include "stdlib.h"
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>

using namespace std;

/****************************************************************************************************/

// 마을의 갯수
int N;

// 머무른 일자
int D;

// 시작 지점 및 현재 위치
int ST;

// 마을 연결 상태
int arr[50][50];

// 마을에 연결된 길의 갯수
int adj[50];

// 특정 일이 지난 후에 특정 마을에서 있을 확률 [day][town]
double cache[101][50];

// 특정 일(days)이 지난 후에 특정 마을(cur)에서 있을 확률
double calc(int days, int cur)
{
	// 기저 케이스
	if (days == 0)
		return (cur == ST ? 1.0 : 0.0);

	// 메모이제이션
	double& ret = cache[days][cur];
	if (ret > -0.5)
		return ret;
	ret = 0;

	for (int prev = 0; prev < N; ++prev)
		if (arr[cur][prev])
			ret += calc(days - 1, prev) / adj[prev];

	return ret;
}

// 캐시 초기화
void preCalc()
{
	fill_n(&cache[0][0], 101 * 50, -1);

	for (int i = 0; i < N; ++i)
	{
		int rowCnt = 0;
		for (int j = 0; j < N; ++j)
			if (arr[i][j])
				rowCnt += 1;
		adj[i] = rowCnt;
	}
}

void inputHandler()
{
	cin >> N;
	cin >> D;
	cin >> ST;

	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			cin >> arr[i][j];

	preCalc();
}

void outputHandler()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		int town;
		cin >> town;
		printf("%.12f ", calc(D, town));
	}
	cout << endl;
}

int main()
{
	int cases;
	cin >> cases;
	while (cases--)
	{
		inputHandler();

		outputHandler();
	}

	return 0;
}