NUMB3RS

두니발 박사의 탈옥 문제를 두 가지 방식으로 풀었다.

첫번째는 책에 나온 DP 를 활용한 방법,

두번째는 내가 직접 푼 방법.

책에 나온게 훨씬 더 깔끔하다.

책에서는 두니발이 이동했을 법한 경로를 추적하여 모든 경로를 DP를 활용하여 구한다. 이 중 유효한 경로들의 확률값 계산을 재귀호출의 리턴값을 이용하여 해결했다.

나의 경우엔 그냥 무식하게 풀었다. A 마을에서 B 마을로 이동할 확률을 계산한 2차원 배열을 만들고, 하루가 지날 때마다 각 마을에 이동했을 확률을 계산하였다. 덕분에 3중 for문 (ㄷㄷ) 을 시전하였다. 

Time Complexity 는 n^2 * d 로 동일하지만 코드의 가독성을 볼 땐 종만 아저씨의 코드가 훨씬 깔끔하고 우아하다.

ps) DP를 구현하다가 기저 사례를 cache 값 참조 이후에 검사하였는데, 이 과정에서 오류가 났다. 왜 그런가 하니, cache 값을 먼저 참조하고, ret = 0.0; 을 실행시켜버리는 것이었다. 즉, 기저 사례 검사 코드에 막혀서 실행되지 않았어야 할 cache 값 초기화 과정이 실행 되어버린 것이었다. 앞으로 코딩할 땐 cache 값 유실에 대해 더 신경쓰고, 기저 사례 판별을 되도록 제일 먼저 해야겠다.

DP를 이용한 풀이

#include <iostream>
#include <iomanip>

using namespace std;

const int MAX_TOWN_NUM = 50;
const int MAX_DAY_NUM = 100;
double cache[MAX_TOWN_NUM][MAX_DAY_NUM];

int N = 0, D = 0, P = 0;
int **linked = NULL;
int T = 0;
int *Q = NULL;
int subQ = 0;
int degree[MAX_TOWN_NUM];

double search(int here, int days);

int main()
{
	int caseNum = 0;

	cin >> caseNum;

	for (int cIter = 0; cIter < caseNum; cIter++)
	{
		for (int i = 0; i < MAX_TOWN_NUM; i++)
			for (int j = 0; j < MAX_DAY_NUM; j++)
				cache[i][j] = -1.0;

		cin >> N >> D >> P;

		linked = new int*[N];

		for (int i = 0; i < N; i++)
		{
			linked[i] = new int[N];
		}
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				cin >> linked[i][j];

		cin >> T;
		Q = new int[T];
		for (int i = 0; i < T; i++)
		{
			cin >> Q[i];
		}

		int degCount = 0;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
				if (linked[i][j] == 1) degCount++;
			degree[i] = degCount;
			degCount = 0;
		}

		// Process
		for (int i = 0; i < T; i++)
		{
			subQ = Q[i];
			cout << setprecision(8) << fixed << search(subQ, D) << " ";
		}
		cout << endl;

		// Dispose
		for (int i = 0; i < N; i++)
			delete[] linked[i];
		delete[] linked;

		delete[] Q;
	}
}

double search(int here, int days)
{
	if (days == 0) return (here == P) ? 1.0 : 0.0;

	double &ret = cache[here][days];
	if (ret != -1) return ret;

	ret = 0.0;

	for (int there = 0; there < N; there++)
		if (linked[here][there] == 1) ret += search(there, days - 1) / degree[there];

	return ret;

}

3중 for 문을 이용한 풀이

#include <iostream>
#include <iomanip>

using namespace std;

int N = 0, D = 0, P = 0;
int **linked = NULL;
double **nextPos = NULL;
int T = 0;
int *Q = NULL;

double *curTownPos = NULL;

void calcNextPos();
void findDunibal(int startTown, int day);

int main()
{
	int caseNum = 0;

	cin >> caseNum;

	for (int cIter = 0; cIter < caseNum; cIter++)
	{
		cin >> N >> D >> P;

		linked = new int*[N];
		nextPos = new double*[N];

		for (int i = 0; i < N; i++)
		{
			linked[i] = new int[N];
			nextPos[i] = new double[N];
		}
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				cin >> linked[i][j];

		cin >> T;
		Q = new int[T];
		for (int i = 0; i < T; i++)
		{
			cin >> Q[i];
		}

		// Process
		calcNextPos();
		findDunibal(P, D);

		for (int i = 0; i < T; i++)
			cout << setprecision(8) << fixed << curTownPos[Q[i]] << " ";
		cout << endl;

		// Dispose
		for (int i = 0; i < N; i++)
			delete[] linked[i];
		delete[] linked;

		delete[] Q;
	}
}

void findDunibal(int startTown, int day)
{
	curTownPos = new double[N];
	for (int i = 0; i < N; i++)
	{
		if (i != startTown) curTownPos[i] = 0;
		else curTownPos[i] = 1;
	}

	double *nextTownPos = new double[N] {0, };

	for (int d = 0; d < day; d++)
	{
		for (int i = 0; i < N; i++)
			nextTownPos[i] = 0;

		// Calculate case of one day pass
		for (int t = 0; t < N; t++)
		{
			for (int next = 0; next < N; next++)
			{
				if (next == t) continue;
				nextTownPos[next] += curTownPos[t] * nextPos[t][next];
			}
		}

		for (int t = 0; t < N; t++)
			curTownPos[t] = nextTownPos[t];
	}
}

void calcNextPos()
{
	double linkCnt = 0;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
			if (linked[i][j] == 1) linkCnt++;

		if (linkCnt == 0) continue;

		for (int j = 0; j < N; j++)
			nextPos[i][j] = linked[i][j] / linkCnt;

		linkCnt = 0;
	}
}

Numb3rsInput.txt

Numb3rsOutput.txt