Problem Solving/BOJ(백준)
[BOJ]백준 1405번: 미친 로봇
이진2
2021. 2. 7. 01:35
1405번: 미친 로봇
첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자
www.acmicpc.net
로봇이 동서남북으로 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