[BOJ]백준 1405번: 미친 로봇

www.acmicpc.net/problem/1405

1405번: 미친 로봇

로봇이 동서남북으로 N번 움직일 수 있다고 할 때, 이동 경로가 단순할 확률(이미 방문한 곳을 방문하지 않을 확률)을 구하는 문제이다.

N이 14 이하의 자연수이기 때문에, 최대 4^14(268,435,456)가지의 이동 경우의 수가 나온다.

즉, 1억번 이하이므로 모든 경우에 대해 조사하면서 단순한지 아닌지 검사해주었다.

출처: 쿠키런 오븐브레이크

백트래킹을 이용해서 특정 좌표의 방문/미방문을 갱신해주었고, 서로 다른 좌표를 N개 방문했을 경우(recursive function의 depth가 N이 되었을 경우)에 정답 확률값을 증가시켰다.

좋은 문제인 것 같다

#include <cstdio>
#include <math.h>
typedef struct {
	int x, y;
}point;
bool visit[50][50];
double ans, prob[4];
int n, cnt, dx[] = { 1,-1,0,0 }, dy[] = { 0,0,1,-1 };
void func(point cur, int dep, double a) {
	if (dep == n) {
		ans += a;
		return;
	}

	visit[cur.y][cur.x] = 1;
	for (int i = 0; i < 4; i++) {
		int nx = cur.x + dx[i], ny = cur.y + dy[i];
		if (visit[ny][nx])continue;

		func({ nx,ny }, dep + 1, a * prob[i]);
	}
	visit[cur.y][cur.x] = 0;
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < 4; i++) {
		double k;
		scanf("%lf", &k);
		prob[i] = (double)k / 100;
	}
	func({ 25,25 }, 0, 1);
	printf("%.10lf", ans);
	return 0;
}

Time Complexity: O(N^4), ∀N<=14