동적 계획법 - 13. 두니발 박사의 탈옥

문제 : 두니발 박사의 탈옥 (난이도 : 中)

 

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

 

 분석

이 문제는 학부 때 확률과 통계를 수강했던 사람이면 마르코프 연쇄(Markov Chain)를 생각할 수 있을 것이다.

 

앞서 푼 문제를 참고하면 확률을 처리하는데 큰 문제는 없을 것이다.

2021/01/03 - [알고리즘 문제 해결 전략] - 동적 계획법 - 10. 우물을 기어오르는 달팽이

동적 계획법 - 10. 우물을 기어오르는 달팽이

 

search(days, num) = 탈옥 d일 후 두니발 박사가 num 마을에 있을 확률이라 할 때, search를 다음과 같은 점화식으로 표현할 수 있다.

 

search 함수 점화식

adj(num)은 num 마을에 인접한 마을의 집합이다.

 

 구현

int A[51][51];
int Q, D, N;

// n번 마을에 연결된 다른 마을의 수를 반환한다.
int connected(int n)
{
	int ret = 0;
	for (int i = 0; i < N; i++)
	{
		if (A[n][i] == 1) ret++;
	}
	return ret;
}

double cache[101][51];
// D날에 Q마을에 있을 확률을 반환한다.
double search(int days, int num)
{
	// base case
	if (days == D)
	{
		if (num == Q) return 1;
		else return 0;
	}
	// memoizaiton
	double& ret = cache[days][num];
	if (ret != -1) return ret;
	ret = 0;
	int s = connected(num);
	for (int i = 0; i < N; i++)
	{
		if (A[num][i] == 1)
		{
			ret += (1.0 / s) * (search(days + 1, i));
		}
	}
	return ret;
}

int main()
{
	int c;
	cin >> c;
	while (c--)
	{
		int P;
		cin >> N >> D >> P;
		// input data
		memset(A, 0, sizeof(A));
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				cin >> A[i][j];
			}
		}

		int T;
		cin >> T;
		while (T--)
		{
			// double형 이므로 이중 for문으로 초기화
			// 매번 cache를 초기화해야 된다.
			for (int i = 0; i < 101; i++)
			{
				for (int j = 0; j < 51; j++)
				{
					cache[i][j] = -1;
				}
			}
			cin >> Q;
			printf("%.10lf ", search(0, P));
		}putchar('\n');
	}

	return 0;
}