[백준/C++] 1405. 미친 로봇

문제 

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

1405번: 미친 로봇

로봇이 4방향 (동서남북)으로 각각 이동할 확률과, 이동 횟수가 주어질 때 

로봇이 한 번 방문한 곳을 다시 방문 하지 않을 확률을 구하는 문제이다. 

풀이

가능한 모든 이동 경로를 탐색하면서 이전에 방문했던 칸을 다시 방문하지 않은 이동경로의 확률을 구해서 모두 더하면 된다. 

DFS로 풀었다고 생각했는데, 백트래킹이라고 한다..? 

내가 이해하기로는 N번 이동하는 걸 탐색한다고 할 때 

매번 길이 N만큼 끝까지 탐색하면 DFS, 중간에 특정 조건을 만족하지 않는 case를 버리고 탐색하지 않는 것은 백트래킹이라고 하는 것 같다. 

 

DFS로 탐색하면서, 중간에 visited배열 값이 1인 곳을 방문하면 탐색을 종료했다. 이동을 N번 했을 때, (N번 동안 중복 방문이 없었음) 해당 이동 경로의 확률을 result에 더했다. 

 

코드

#include <cstdio>
#include <iostream>

#define sc scanf
using namespace std;

bool visited[29][29]; // 14+1+14 = 29
int N;
double per[4];
int dr[4] = { 0,0,1,-1 }; // E W S N
int dc[4] = { 1,-1,0,0 };
double result = 0;
void DFS(int startR, int startC, int n, double p) {
	if (n == N) {
		result += p;
		return;
	}
	for (int i = 0;i < 4;i++) {
		int nextR = startR + dr[i];
		int nextC = startC + dc[i];

		if (visited[nextR][nextC]) continue;
		visited[nextR][nextC] = 1;	
		DFS(nextR, nextC, n + 1, p * per[i]);
		visited[nextR][nextC] = 0;
	}
}
int main() {
	sc("%d", &N);
	for (int i = 0;i < 4;i++) {
		sc("%lf", &per[i]);
		per[i] /= 100.0;
	}
	visited[14][14] = 1;
	DFS(14,14, 0, 1);
	printf("%.10lf\n", result);
	return 0;
}

결과