[ BOJ 백준 1405번 - 미친 로봇 ] 해설 및 코드

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

백준 1405번 미친로봇

1405번: 미친 로봇

 

 

목적

로봇의 이동경로가 단순(방문한 곳을 재방문 하지 않음)할 확률을 구하자.

 

접근법

1. 완전탐색 알고리즘으로,동서남북 네 방향으로 이동할 수 있는 모든 경우에 해당하는 확률의 합을 구한다.

 

*주의 : cout.precision(10); 코드를 사용하여 문제 조건에 해당하는 오차 범위로 변경해주자.

 

#include<iostream>
 
using namespace std;
 
bool b[30][30]={};
int di[]={0,0,1,-1},dj[]={1,-1,0,0};
double p[4];
 
double calc(int i,int j, int n){
    if(b[i][j])return 0;
    if(n==0)return 1;
    b[i][j]=true;
    double ret=0;
    for(int k=0;k<4;++k)ret+=(p[k]*calc(i+di[k],j+dj[k],n-1));
    b[i][j]=false;
    return ret;
}
 
int main(){
    int n;cin>>n;
    for(int i=0;i<4;++i){
        int tmp;cin>>tmp;
        p[i]=(double)tmp/100;
    }
    cout.precision(10);
    cout<<calc(15,15,n);
 
}