[BOJ 1405] 미친 로봇(Java, DFS, 간단한 풀이)

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

1405번: 미친 로봇

 

1. 로봇은 방문했던 곳을 방문하지 않고 정해진 횟수의 이동을 끝내는 경우를, 단순한 경로라고 한다. 단순한 경로들을 찾아가면서, 발생할 확률들의 합을 구하면 정답이 된다.

 

 

 

2. 로봇의 방문을 DFS를 통해서 전체 탐색을 하도록 한다.

 

---

 

해설코드(Java).

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    static int N;
    static int[][] op = {{0,1},{0,-1},{1,0},{-1,0}};
    static double[] perArr = {0,0,0,0};
    static boolean[][] chk; 
    
    public static double dfs(int r, int c, int move, double percent){
        if(move == N)
            return percent;
            
        double result = 0;
        for(int i = 0; i < op.length; i++){
            int nr = r + op[i][0];
            int nc = c + op[i][1];
            
            if(chk[nr][nc] == false)
            {
                chk[nr][nc] = true;
                result += dfs(nr, nc, move + 1, percent * perArr[i]);
                chk[nr][nc] = false;
            }
        }
        
        return result;
    }
 
    public static void main (String[] args) throws java.lang.Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] sArr = br.readLine().split(" ");
        chk = new boolean[14 * 2 + 1][14 * 2 + 1];
        
        for(int i = 0; i < chk.length; i++){
            for(int j = 0; j < chk[i].length; j++){
                chk[i][j] = false;
            }
        }
        
        N = Integer.valueOf(sArr[0]);
        perArr[0] = Double.valueOf(sArr[1]) / 100;
        perArr[1] = Double.valueOf(sArr[2]) / 100;
        perArr[2] = Double.valueOf(sArr[3]) / 100;
        perArr[3] = Double.valueOf(sArr[4]) / 100;
        
        chk[14][14] = true;
        bw.write(dfs(14,14,0,1) + "\n");
 
        bw.flush();
    }
}