8.16_두니발 박사의 탈옥_NUMB3RS

문제 설명

algospot.com :: NUMB3RS

• 두니발 박사는 검문을 피해 산길로만 이동한다.
• 두니발 박사는 교도소를 탈출한 당일, 교도소와 인접한 마을 하나로 도망쳐 은신한다.
• 두니발 박사는 이후 매일 인접한 마을로 움직여 은신한다.
• 산길(간선)과 마을(노드)가 주어진다.
• n개의 마을이 주어진다.(2 <= n <= 50)
• 탈출부터 지금까지 지난 일 수 d가 주어진다.(1 <= d <= 100)
• 교도소가 있는 마을의 번호 p가 주어진다.
• i번 마을에서 j번 마을을 잇는 산길에 대한 정보 A행렬이 주어진다.
• 확률을 계산할 마을의 번호 q가 t개 주어진다.

=> d일 후 마을 q에 두니발 박사가 있을 확률을 구하기

 

 

문제 풀이

재귀 함수 규칙 찾기

 

문제에 주어진 그림에서

 

1. 0번 마을에 첫째날 두니발 박사가 도달할 확률은 1/5이다.

1/5의 5는 교도소로 주어진 3번 마을의 간선의 개수이다.

즉, 3번 마을 -> 1번 마을로 오는 확률은 1/[3번 마을의 간선의 개수] 인것이다.

 

2. 0번 마을에 둘째날 두니발 박사가 도달하려면

두니발 박사가 첫째날에 0번 마을과 인접한 1, 2, 3번 마을에 있어야 둘째날 0번 마을에 도달할 수 있다.

즉, 0번 마을에 둘째날 두니발 박사가 도달할 확률은

(첫째날 1번 마을에 도달할 확률 x 1번에서 0번으로 오는 확률 ) +

(첫째날 2번 마을에 도달할 확률 x 2번에서 0번으로 오는 확률 ) + 

(첫째날 3번 마을에 도달할 확률 x 3번에서 0번으로 오는 확률 ) 

으로 구할 수 있다.

 

1번과 2번에서 " d번째날 n번 마을에 도달 확률"이  반복되는 것을 알 수 있다.

이를 작은 문제로 쪼개어 재귀 함수로써 풀 수 있다.

 

 

기저 조건

 

d번째날 n번 마을부터 시작해서 d-1번째날, d-2 번째날, ... , 첫째날 으로 내려가는데

첫째날에는 교도소로 주어진 번호 p와 연결되어 있어야 두니발 박사가 움직일 수 있는 확률이 생긴다.

 

 

메모이제이션

 

d번째날 n번 마을에 도달할 확률에 대해서 중복적으로 접근할 수 있기에

메모리에 d, n 과 관련된 확률 값을 저장하여 중복 연산을 방지하고 시간을 단축할 수 있다.

 

 

문제 풀이 코드

#include <iostream>
#include <string.h>

using namespace std;

int n, d, p, t;
int links[50][50];			// 간선 정보
int linkCnt[50];			// 간선 개수
double percentage[50][101];	// index, day 의 확률

double calPercentage(int index, int day) {
	double& ret = percentage[index][day];
	if (ret != -1.0)
		return ret;

	if (day == 1) {			// 첫째 날
		if (links[p][index] == 1)	// 교도소와 연결되어 있어야 확률 반환
			return (1.0 / (double)linkCnt[p]);
		return 0.0;			// 아니면 0
	}

	ret = 0;
	for (int i = 0; i < n; ++i) {
		if (links[i][index] == 1) {
			ret += ((1.0 / (double)linkCnt[i]) * calPercentage(i, day - 1));
		}
	}

	return ret;
}

int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(0);

	int C;
	cin >> C;
	for (int tc = 1; tc <= C; ++tc) {
		cin >> n >> d >> p;
		memset(linkCnt, 0, sizeof(linkCnt));
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j <= d; ++j) {
				percentage[i][j] = -1.0;	// 초기화
			}
		}

		for (int i = 0; i < n; ++i) {		// 간선 입력받기
			for (int j = 0; j < n; ++j) {
				cin >> links[i][j];
				if(links[i][j] == 1)
					++linkCnt[i];
			}
		}

		cin >> t;
		for (int i = 0; i < t; ++i) {
			int num;
			cin >> num;
			calPercentage(num, d);
			cout << fixed;					// 출력 소숫점 아래 8자리로 고정
			cout.precision(8);
			cout << percentage[num][d];
			if (i != t - 1)
				cout << " ";
		}
		cout << endl;
	}
	return 0;
}