[BOJ/백준][Gold5] 1405 : 미친 로봇 (C++)

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

1405번: 미친 로봇

 

[난이도] Gold5
[유형] 브루트포스

[풀이]
DFS 재귀함수를 이용해서 가능한 모든 경우를 구해준다. 일반 DFS와 다르게 함수 return시 visit[i]=0으로 다시 설정해주어야 한다. 왜냐하면 새로운 경우의 경로에서는 이전에 방문했던 곳도 다시 방문할 수 있기 때문이다.
소숫점 9자리까지 출력해야 하는것에 주의해야한다.

 

  
    #include <cstdio>

    int N,dy[4]={0,0,1,-1};
    int dx[4]={1,-1,0,0},visit[40][40];
    int p[4],cnt;
    double ans;
    void sol(int y,int x,int k,double pr){
        visit[y][x]=1;
        if(k==N){
            visit[y][x]=0;
            cnt++;
            ans+=pr;
            return;
        }
        
        for(int i=0;i<4;i++){
            int ny=y+dy[i], nx=x+dx[i];
            if(!visit[ny][nx]){
                sol(ny,nx,k+1,pr*(p[i]/(double)100));
            }
        }
        visit[y][x]=0;
    }
    int main(){
        scanf("%d",&N);
        for(int i=0;i<4;i++) scanf("%d",&p[i]);
        sol(17,17,0,1);
        printf("%.11f",ans);
    }

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/1405.cpp