백준 1405 미친 로봇 c++ 풀이 - DFS

4개의 방향을 확률로 움직이는 미친로봇이다. 

EWSN 순으로 확률(%)가 입력되고 당연하게도 모든 확률의 합은 1(100%) 이다.

움직인 수 n 이 최대 14까지 늘어나기 때문에 단순히 경우의 수로 계산해보면 4 ^ 14 이므로

탐색에만 약 2억 번의 연산이 필요하다.

 

하지만 우리가 원하는 것은 경로가 단순하지 않을 확률(혹은 단순할 확률)이므로 중간의 브렌치(분기)들을

자르면서 가면 경우의 수가 확 줄게된다.

 

예를 들어 E 방향으로 한 칸 갔다가 바로 W 방향을 가는 경우 반드시 단순하지 않은 경로가 되므로

(원점이 아닌) 점에서 갈 수 있는 방향은 3가지로 제한되므로 3^14 로 줄어든다. 

이는 기껏해야 백만 단위이므로 충분히 수행할만하다.

그러므로 DFS를 통한 완전탐색으로 문제를 수행한다.

 

DFS로 접근하는 이유는, n이 최대 14이기 때문에 깊이가 최대 14로 충분히 수행할만하기 때문이다.

 

논리는 다음과 같다.

 

단순한 경로 찾기

1. 원점에서 출발한다.

2. 다음 방향을 정한다.

3. 방문하지 않은 곳이라면 움직인다.

4. 2~3을 반복하다가 최대 깊이(n)까지 도달하면 그 경로의 확률을 계산하여 답에 더한다.

 

혹은 다음과 같다.

 

단순하지 않은 경로 찾기

1. 원점에서 출발한다.

2. 다음 방향을 정한다.

3. 방문한 곳이라면 그 경로의 확률을 계산하여 모두 더한 후 출력 전에 뺀다.

 

둘의 논리는 서로 반대이지만 결과는 같다.

int MAP[30][30];
int n;
double ans;
int dir[4];
int dy[4] = { 0,0,-1,1 };
int dx[4] = { 1,-1,0,0 };
int road[15] = { -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 };

int DFS(int y,int x, int num) {
	if (num == n) {
		double tmp = dir[road[0]];
		for (int j = 1; j < n; j++) {
			tmp *= dir[road[j]];
		}
		for (int j = 0; j < n; j++) {
			tmp /= 100.0;
		}
		//printf("y : %d x : %d tmp : %lf\n", y, x, tmp);
		ans += tmp;
		return 0;
	}
	MAP[y][x] = 1;
	//printMAP();
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (!MAP[ny][nx]) {
			road[num] = i;
			DFS(ny, nx, num + 1);
			MAP[ny][nx] = 0;
			road[num] = -1;
		}
	}
	return 0;

}

 

DFS는 위와 같이 구성한다.

현재 있는 곳과 움직인 횟수를 PARAMETER로 받는다.

if (num==n) 은 종료조건으로 지정된 횟수만큼 움직였을 경우 그 경로의 확률을 구한다.

(각 방향으로 이동할 확률을 모두 곱하면 됨)

 

굳이 배열을 사용해서 저장하지 않고도 param으로 전달하여 구할 수도 있겠지만, 눈으로 보고 싶어서 배열로 정했다.

또한 중요한 것은 다음 움직일 방향(ny ,nx)을 구할 때, i의 값 0,1,2,3 이 각각 EWSN의 방향과 일치해야 동작한다.

EWSN의 방향은 dx, dy 배열에 미리 정해놓고 i로만 접근할 수 있게 구성했다.

 

전체코드

#include <stdio.h>
#include <iostream>
#include <stdlib.h>

int MAP[30][30];
int n;
double ans;
int dir[4];
int dy[4] = { 0,0,-1,1 };
int dx[4] = { 1,-1,0,0 };
int road[15] = { -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1 };

void printMAP() {
	for (int i = 0; i <=2*n ; i++) {
		for (int j = 0; j <=2*n; j++) {
			printf("%d", MAP[i][j]);
		}
		printf("\n");
	}
	printf("\n======================================================================\n");
}

int DFS(int y,int x, int num) {
	if (num == n) {
		double tmp = dir[road[0]];
		for (int j = 1; j < n; j++) {
			tmp *= dir[road[j]];
		}
		for (int j = 0; j < n; j++) {
			tmp /= 100.0;
		}
		//printf("y : %d x : %d tmp : %lf\n", y, x, tmp);
		ans += tmp;
		return 0;
	}
	MAP[y][x] = 1;
	//printMAP();
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (!MAP[ny][nx]) {
			road[num] = i;
			DFS(ny, nx, num + 1);
			MAP[ny][nx] = 0;
			road[num] = -1;
		}
	}
	return 0;

}

int main() {
	scanf("%d", &n);
	//EWSN
	scanf("%d %d %d %d", &dir[0], &dir[1], &dir[2], &dir[3]);
	DFS(n, n, 0);
	printf("%.9lf", ans);

}