백준 1405: 미친 로봇

문제 요약

통제 할 수 없는 미친 로봇이 평면위에 있다. 그리고 이 로봇은 N번의 행동을 취할 것이다.

각 행동에서 로봇은 4개의 방향 중에 하나를 임의로 선택한다. 그리고 그 방향으로 한 칸 이동한다.

로봇이 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 한다. (로봇이 시작하는 위치가 처음 방문한 곳이다.) 로봇의 이동 경로가 단순할 확률을 구하는 프로그램을 작성하시오. 예를 들어, EENE와 ENW는 단순하지만, ENWS와 WWWWSNE는 단순하지 않다. (E는 동, W는 서, N은 북, S는 남)

문제 분류

• 수학
• 그래프 이론
• 브루트포스 알고리즘
• 그래프 탐색
• DFS
• 백트래킹
• 확률론

문제 풀이

우선 크게 보자면 n지 탐색하는 중간에 두 지 경우가 존재한다. 이번 탐색을 해도 단순한 경로가 될 경우와 이번 탐색을 통해 단순한 경로가 깨질 경우이다.

전자는 새로운 곳을 방문한 경우고, 후자는 이미 방문한 곳을 재방문하는 경우이다. 이때 재방문하여 단순하지 않은 경로가 될 경우 해당 경우의 확률은 n번까지 방문하지 않아도 바로 알 수 있다. 즉, 재방문하여 단순하지 않은 경로가 되면 그 경로가 될 확률을 구해서 누적시킨 뒤, 바로 탐색을 종료하면 된다. 단순한 경로를 끝까지, n번 탐색하여 확률을 구해서 누적시키는 것보다 단순하지 않은 경로를 탐색하여 해당 확률을 누적시키고 1에서 해당 확률의 차로 단순한 경로의 확률을 구하는 방법을 택했다.

동,서,남,북으로 이동하는데 각각 방향의 확률이 0 초과일때만 탐색하도록 하였고, 매개변수에 확률을 두어 현재 탐색까지 올 확률을 구해주었다. 탐색 횟수도 매개변수로 두어 탐색 횟수가 n이 되면 바로 탐색을 종료하도록 하였고, 재방문시 확률을 누적시키고 탐색을 종료시켰다.

입력 n의 최대는 14. 즉, 동쪽으로 14번 혹은 서쪽으로 14번 연속나올 수 있으므로 출발위치를 가운데로 잡고 상하좌우로 14개, 최대 크기가 [29][29]인 배열이 필요하게 된다. 여기서 출발하는 가운데 위치는 [14][14]가 된다.

풀이 코드

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

using namespace std;

string ary[5];
bool visited[29][29];
int dir[4][2] = { {0,1},{0,-1},{-1,0},{1,0} };
double p[4], res = 0;
int n, in;

void dfs(int x, int y, int fcnt, double pi) {
	if (visited[y][x]) {
		res += pi;
		return;
	}
	if (fcnt == n) return;
	visited[y][x] = true;
	int nx, ny;
	for (int i = 0; i < 4; i++) {
		if (p[i] > 0) {
			nx = x + dir[i][1];
			ny = y + dir[i][0];
			dfs(nx, ny, fcnt + 1, pi * p[i]);
		}
	}
	visited[y][x] = false;
}

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < 4; i++) {
		scanf("%d", &in);
		p[i] = in / 100.;
	}
	dfs(14, 14, 0, 1);
	printf("%.10lf", 1. - res);

	return 0;
}