BOJ 1405 - 미친로봇(C++)

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

1405번: 미친 로봇

풀이

N이 14보다 작거나 같기 때문에 시작점을 (14, 14)로 설정

dfs를 사용하여 해당방향으로 갈 확률을 곱해주는 방식으로 진행

ex) 테스트 케이스 N=2, [25, 25, 25, 25]의 경우 :

  (동서남북의 확률이 같아 처음 한방향의 확률값 x 4로 계산 가능)

  1/4 x (1/4 + 1/4 +1/4) x 4 = 0.75

절대/상대 오차는 10-9 -> 소수점 아래 10자리까지 허용이므로 cout.precision(10)사용

#include <iostream>

#define MAX 29
using namespace std;

int N;
double dir_percent[4];
int dy[] = {0,0,1,-1};
int dx[] = {1,-1,0,0};
bool visit[MAX][MAX];

double dfs(int y, int x, int dis) {
    if (dis >= N) {
        return 1.0;
    }
    double result = 0.0;
    visit[y][x] = true;

    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (visit[ny][nx])continue;
        //현재 확률 + 다음 방향에 대한 확률 
        result+=(dir_percent[i] * dfs(ny, nx, dis + 1));
    }
    visit[y][x] = false;
    return result;
}

int main() {
    cin >> N;
    
    int temp;
    for (int i = 0; i < 4; i++) {
        cin >> temp;
        dir_percent[i] = temp / 100.0;
    }
    
    cout.precision(10);//소수점 10자리 제한
    cout << dfs(14, 14, 0);
    return 0;
}