1405번: 미친 로봇

문제 설명

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

1405번: 미친 로봇

[문제]

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

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

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

 

[입력]

 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고,  모든 확률은 100보다 작거나 같은 자연수 또는 0이다. 그리고, 동서남북으로 이동할 확률을 모두 더하면 100이다.

 확률의 단위는 %이다.

 

[출력]

 첫째 줄에 로봇의 이동 경로가 단순할 확률을 출력한다. 절대/상대 오차는 10-9 까지 허용한다.

 

[예제 입력 1]

2 25 25 25 25

[예제 출력 1]

0.75

---

풀이

 처음엔 확률과 경우의 수를 통해 문제를 풀어보려 했으나 빠르게 포기하고, 완전탐색으로 문제를 해결했다. 완전 탐색으로 문제를 해결하는 것은 그렇게 어렵지 않은데, 단순히 상하좌우 좌표 이동을 하여 함수를 재귀호출하고, 해당 위치가 이미 중복됐다면 그대로 종료, 또는 끝까지 이동을 모두 했을 때 최종 확률을 더해주면 된다. 해당 함수가 끝날 때는 다른 탐색을 위해 중복 체크를 해제해준다.

 다만 출력 때 소수점을 위해, 이를 수정하여 결과를 출력해주면 된다. 

 

#include <iostream>

using namespace std;

int visited[29][29] = { 0, };
int N;
double east, west, south, north;//동서남북 확률

void move(int r, int c, int moveCount, double probability, double& result) {

	if (visited[r][c] == 1) //이미 온 곳이면
		return;

	if (moveCount == N) {//모든 이동을 끝냈다면
		result += probability;
		return;
	}

	//방문 체크
	visited[r][c] = 1;

	//동서남북 이동
	move(r + 1, c, moveCount + 1, probability * south, result);
	move(r - 1, c, moveCount + 1, probability * north, result);
	move(r, c + 1, moveCount + 1, probability * east, result);
	move(r, c - 1, moveCount + 1, probability * west, result);

	//방문 해제
	visited[r][c] = 0;
}


int main() {
	double result = 0;

	//입력 후 확률 값 조정
	cin >> N >> east >> west >> south >> north;
	east *= 0.01;
	west *= 0.01;
	south *= 0.01;
	north *= 0.01;

	move(14, 14, 0, 1, result);

	//소수점 자리 설정 후 출력
	cout << fixed;
	cout.precision(10);
	cout << result;

	return 0;
}

---

결과