[C++] 알고스팟/동적계획법 - 두니발 박사의 탈옥

문제 링크

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

algospot.com :: NUMB3RS

 

인접한 모든 마을을 dfs 방식과 같이 탐색하고 들어간 위치와 날짜를 메모이제이션을 해줍니다.

인접한 마을에서 날짜 d 만큼 지났을 때 감옥에 위치했는지에 대한 확률을 구하고 모든 인접한 마을에 대한 확률을 더해 최종 확률을 구해줍니다.

 

 

구현 코드

 

	#include <iostream>
	#include <cstring>
	#include <vector>
	#define endl '\n'
	#define fastio cin.sync_with_stdio(false); cin.tie(nullptr)
	using namespace std;
	double cache[51][101];
	int connected[51][51];
	int deg[51];
	int n,d,p,q;
	//감옥에서부터 시작하지 않고
	//다른 마을에서부터 시작하여 감옥으로 도착하는 경우를 확인.
	double search(int here, int days){
	if(days == 0) return (here == p ? 1.0 : 0.0);
	double &ret = cache[here][days];
	if(ret > -0.5) return ret;
	ret = 0.0;
	//현재위치와 인접한 경로를 모두 방문하여 d일째에 감옥에 위치할 확률을 구한다.
	for(int there=0;there<n;++there)
	if(connected[here][there])
	ret += search(there, days-1) / deg[there];
	return ret;
	}
	int main(){
	fastio;
	int _;
	cin >> _;
	while(_--){
	memset(cache, -1, sizeof(cache));
	memset(deg, 0, sizeof(deg));
	cin >> n >> d >> p;
	for(int i=0;i<n;i++){
	for(int j=0;j<n;j++){
	cin >> connected[i][j];
	//i번째 마을과 연결된 마을의 개수를 더해준다.
	deg[i] += connected[i][j];
	}
	}
	cin >> q;
	while(q--){
	int h;
	cin >> h;
	cout.precision(8);
	cout << search(h, d) << " ";
	}
	cout << endl;
	}
	}

view raw numb3rs.cpp hosted with ❤ by GitHub