[BOJ 1405] 미친 로봇

acmicpc.net/problem/1405

1405번: 미친 로봇

당분간 글을 쓸 생각이 없었지만 예쁜 문제를 발견해 소장할 겸 가져왔다. ㅎ

 

우선 30×30 크기의 배열을 만들고, (15,15)에서 출발한다고 생각하자. 이제 간단한 재귀함수 느낌의 백트래킹을 해주면 답을 구할 수 있다. (X, Y)에서 K번 이동했을 때의 기댓값은 (X, Y-1), (X, Y+1), (X-1, Y), (X+1, Y)에서 K-1번 이동했을 때의 기댓값에 각각의 확률을 곱한 다음 전부 더해주면 된다. 이때 종료 조건은 이미 방문한 점에 방문했을 때나, 이동 횟수를 소진했을 때로 잡을 수 있다. 기댓값을 재귀적으로 구하는 과정에서 오차가 커질 것을 예상했지만, 다행히 double형을 사용하는 것만으로 맞을 수 있었다.

 

#include<bits/stdc++.h>
using namespace std;
int n,dx[4]={0,0,1,-1},dy[4]={-1,1,0,0};
double p[4];
bool v[33][33];
double dfs(int x,int y,int k)
{
    if(v[x][y]) return 0;
    if(!k) return 1;
    v[x][y]=true;
    double res=0;
    for(int i=0;i<4;i++) res+=p[i]*dfs(x+dx[i],y+dy[i],k-1);
    v[x][y]=false;
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<4;i++){
        scanf("%lf",&p[i]);
        p[i]/=100;
    }
    printf("%.10f",dfs(15,15,n));
}