Backjoon1405/탐색/DFS(깊이 우선 탐색)

* Part 01 문제 분석

포인트 : 로봇이 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 한다.

ex ) EENE와 ENW는 단순하지만, ENWS와 WWWWSNE는 단순하지 않다. (E는 동, W는 서, N은 북, S는 남)

    로봇의 이동 경로가 단순할 확률을 출력하는 것이기에  단순하지 않은 경로는 빼고 출력한다.

* Part 02 문제 설계

1) 경로를 계산하는 것인데 문제에 이동횟수 N>=14인 자연수라고 했으니, 나는 28*28 이차원 배열을 판으로     만든다. 중심을 시작점으로 둔다.

2) 동,서,남,북의 percentage를 저장할 배열 / walking 하는 횟수 / 총 percentage 3가지 변수 선언

3) 재귀함수(recursive function)을 통해 DFS 알고리즘을 구현한다.

3) 방향에 대한 확률은 각각 곱해서 이동횟수가 충족되었을시에 총 percentage에 더해주고 return

4) return을 하고 또 다른 방향에 대해 나아갈 수 있는 모든 확률 구함

//주의) 단순하지 않은 경로는 제외시켜주는 것이 포인트이다.

* Part 03 문제 풀이

#include <stdio.h>
int dir[4][2] = { { 0, 1 },{ 0, -1 },{ 1, 0 },{ -1, 0 } }; //direction array
double per[4];						//percentage
int arr[29][29] = { 0 };			//28 * 28
int num;							//walking num
double total = 0;					//total percentage
void dfs(int x, int y, int n, double temp) { //using dfs algorithm
	int i, dx, dy;							 
	if (n == num) {
		total += temp;
		return;
	}
	for (i = 0; i < 4; i++) {
		dx = x + dir[i][0];
		dy = y + dir[i][1];
		if (arr[dx][dy] == 1)
			continue;
		arr[dx][dy] = 1;
		dfs(dx, dy, n + 1, temp * per[i]);
		arr[dx][dy] = 0;
	}
}
int main()
{
	int i;
	double temp;
	scanf("%d", &num);
	for (i = 0; i < 4; i++) {
		scanf("%lf", &temp);
		per[i] = temp / 100.0;
	}
	arr[14][14] = 1;
	dfs(14, 14, 0, 1.0);
	printf("%.9lf\n", total);
	return 0;
}