BOJ 1405 - 미친 로봇

링크: https://www.acmicpc.net/problem/1405

문제

동서남북 각 방향으로 이동할 확률이 주어지고, 로봇이 동선을 겹치지 않게 n번 움직일 확률을 구하는 문제이다.

(0, 0)부터 출발한다고 생각하면 동서남북 경계의 끝은 (14, 0), (-14, 0), (0, 14), (0, -14) 일텐데 음수를 없애기위해 출발점을 (15, 15)로 설정하면 편하다.

좌표값을 들고 다니는 이유는 동선이 겹쳐서는 안되기 때문에, 다시 말해 이미 방문한 위치는 다시 방문하지 않도록 하기 위해서이다.

어떤 한 위치에서 생각했을 때, 동쪽으로 이동한다면 동쪽에서 나오는 모든 확률은 (그 위치에서 발생하는 확률 * 동쪽으로 이동할 확률)이 된다. 이걸 동서남북 모든 방향과 모든 위치마다 반복한다면 정답을 구할 수 있다.

코드

	#include <cstdio>
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,1,-1};
	int n, poten[4];
	bool visit[30][30];
	double robot(int step, int y, int x) {
	if (visit[y][x]) return 0;
	if (step >= n) return 1;
	double potential = 0;
	visit[y][x] = true;
	for (int i = 0; i < 4; ++i) {
	int ny = y + dy[i];
	int nx = x + dx[i];
	potential += (poten[i] / 100.0) * robot(step + 1, ny, nx);
	}
	visit[y][x] = false;
	return potential;
	}
	int main() {
	scanf("%d", &n);
	for (int i = 0; i < 4; ++i)
	scanf("%d", &poten[i]);
	printf("%.9lf\n", robot(0, 15, 15));
	return 0;
	}

view raw boj-1405.cpp hosted with ❤ by GitHub