#백준_1405 미친 로봇 - Java 자바

# 유형 : 탐색 

# 난이도 : Gold V

# 쉽게 볼 수 있는 DFS 문제.. 동서남북 방문 안한 곳을 갈 때마다 확률 값을 곱해줘서 매개변수로 넘겨주면서 카운트와 이동 횟수가 일치할 때 합을 해주면 된다. 아무리 풀어도 틀리길래.. 잘 못 풀은 줄 알았는데 확률값이 동/서/남/북 순서로 들어오는데 이걸 안 보고 계속 왜 틀리지 생각했다.. 문제를 꼼꼼히 읽자....

package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p1405 {
    static int N;
    static int prob[] = new int[4];
    static boolean visit[][]=new boolean[30][30];
    static int moveX[] = {1,-1,0,0};
    static int moveY[] = {0,0,1,-1};
    static double result = 0;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        for(int i=0; i<4; i++) {
            prob[i] = Integer.parseInt(st.nextToken());
        }
        visit[15][15]=true;
        dfs(15,15,0,1.0);
        System.out.println(String.format("%.10f", result));
    }
    
    public static void dfs(int i, int j, int cnt, double val) {
        
        if(cnt == N) {
            result += val;
            return;
        }
        
        
        
        for(int d=0; d<4; d++) {
            int newX = j + moveX[d];
            int newY = i + moveY[d];
            if(!visit[newY][newX]) {
                visit[newY][newX]=true;
                dfs(newY, newX, cnt+1, val*0.01*prob[d]);
                visit[newY][newX] = false;
            }
        }
    }
}