알고스팟: 두니발 박사의 탈옥 (ID: NUMB3RS)

[문제 링크]

algospot.com :: NUMB3RS

---

교도소가 있는 마을(P)에서 지난 일수(D)동안 도달할 확률을 계산할 마을(Q)에 도달할 수 있는 경로의 수가 여러 개일 때 확률을 구하기 위해서는 각 경로의 확률을 더해줘야한다는 사실을 몰라서 어려웠던 문제였다.

 

이 사실을 책에서 참고한 것을 제외하면 전체적인 알고리즘을 책을 보지 않고 구현했다는 생각에 뿌듯함과 보람을 느꼈다.

 

필자는 도달할 확률을 계산할 마을(Q)를 시작으로 하여 역순으로 탐색하였다.

---

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

int N, D, P, Q;
double memo[101][51];
bool map[51][51];
int dist[51];

double Solution(int day, int here)
{
	if (here == P && day == 0) return 1;
	if (day == 0) return 0;

	double& ret = memo[day][here];
	if (ret != -1) return ret;

	ret = 0;

	for (int i = 0; i < N; i++)
	{
		int path = map[here][i] * dist[i];
		double temp = 0;
		if (path != 0)
			temp = Solution(day - 1, i) / path;

		ret += temp;
	}
	return ret;
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		memset(dist, 0, sizeof(dist));

		for (int i = 0; i < 101; i++)
			for (int j = 0; j < 51; j++)
				memo[i][j] = -1;

		cin >> N >> D >> P;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
			{
				cin >> map[i][j];
				if (map[i][j]) dist[i]++;
			}

		int T;
		cin >> T;
		while (T--)
		{
			cin >> Q;
			printf("%.8f ", Solution(D, Q));
		}
		printf("\n");
	}

	return 0;
}

알고리즘 200일 프로젝트 - 61 day