Baekjoon 1405 미친 로봇

Link https://www.acmicpc.net/problem/1405

소스 결과 1988 KB / 40 ms

출처 Baekjoon

언어 C++ 17

분류 DFS, 브루트 포스, 탐색

 

설명

통제할 수 없는 미친 로봇이 n번의 행동 중 로봇의 이동 경로가 단순한 경우의 확률을 구해 내는 문제

 

앞선 문제의 경우와 다른 점은 확률을 구해야 한다는 점이 가장 눈에 띈다.

이동 경로를 구해야 되는 문제이기 때문에 BFS/DFS를 사용 해야 한다. 하지만 이번 문제는 최단 경로를 구하는 문제가 아니기에 BFS를 사용하는것은 적절하지 않아보인다.

또한 로봇이 이동 할 수 있는 모든 경로에 대해서 탐색 해야한다. DFS를 진행 하면서 브루트 포스가 자동으로 진행 되기 때문에 크게 유의하지는 않아도 된다.

맵의 크기가 n일 때 DFS를 진행 할 때 맵의 크기는 n * 2 + 1 의 맵을 사용해 주어야 한다. 로봇이 동,서,남,북 으로 전부 움직이는 경우로 생각해야 하기 때문에 시작 점을 포함해 2배의 길이가 필요하기 때문이다.

또한 시작지점을 0,0이 아닌 맵의 정중앙으로 설정해 주어야한다.

 

입력에 있어서 유의할 점은 동, 서, 남, 북 순서로 들어오기 때문에 확률을 저장하는 변수와 방향을 지정할 변수의 값을 일치 시켜야 한다. 이 조건 때문에 한번 틀렸다.

 

출력에 있어서 유의할 점은 소수점이 2자리에서 끝난다고 2자리까지만 출력해주면 안된다. 질문 게시판을 확인하니 소수점 11자리까지 출력해줘야 정답으로 인정해 준다.

 

알고리즘

1. 맵의 크기와, 동, 서, 남, 북으로 이동할 확률을 순서대로 받는다.

2. 시작지점을 맵의 정중앙인 n,n으로 설정후 DFS를 진행한다.

 2 - 1. 목표하는 방향으로 0% 확률이 아니라면 다음 지점이 범위 밖인지, 과거에 진행 했던 지점인지 확인한다.

 2 - 2. 2-1 조건을 만족하는 경우라면 현재까지의 확률 * 해당 방향 확률을 매개변수로 같이 넘겨준다.

 2 - 3. 로봇이 이동할 수 있는 최대 경우로 진행 했다면 현재 방향까지 올 확률을 반환한다.

3. 출력을 고정 소수점 11자리로 설정 후 확률을 출력한다.

 

소스코드

#include <iostream>

using namespace std;

const int MAX = 15;

const short posX[4] = { 1, -1, 0, 0 }; // E W
const short posY[4] = { 0, 0, 1, -1 }; // S N
bool map[MAX * 2 + 1][MAX * 2 + 1];
double percentage[4];
short n;

double dfs(int pos, short x, short y, double curPer)
{
	double res = 0;
	if (pos == n)
	{
		return curPer;
	}
	else
	{
		for (int i = 0; i < 4; i++)
		{
			if (percentage[i] != 0)
			{
				short nextX = x + posX[i];
				short nextY = y + posY[i];

				if (0 <= nextX && nextX < (n * 2 + 1) && 0 <= nextY && nextY < (n * 2 + 1) && !map[nextX][nextY])
				{
					map[nextX][nextY] = true;
					res += dfs(pos + 1, nextX, nextY, curPer * percentage[i]);
					map[nextX][nextY] = false;
				}
			}
		}
	}

	return res;
}

int main()
{
	cin >> n;

	for (int i = 0; i < 4; i++)
	{
		cin >> percentage[i];
		percentage[i] /= 100.0;
	}


	map[n][n] = true;
	cout.precision(11);
	cout << fixed << dfs(0, n, n, 1);

	return 0;
}