미친 로봇 - 1405번

---

 

모든 경로를 확인하면서 백트레킹으로 단순하지 않은 경로를 찾아주었다.

자바에 지수형 표현을 제거하기 위해 BigDecimal을 사용했다.

 

내 코드

package com.company;

import java.io.*;
import java.math.BigDecimal;
import java.util.*;

public class Main {
    static int N;
    static int[][] way = {{-1, 0, 0}, {1, 0, 0}, {0, -1, 0}, {0, 1, 0}};
    static int[][] table = new int[30][30];
    static int x = 15;
    static int y = 15;
    static double answer = 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++) {
            way[i][2] = Integer.parseInt(st.nextToken());
        }

        dfs(0, x, y, 1);
        System.out.println(new BigDecimal(1 - answer));
    }

    static void dfs(int count, int x, int y, double per) {
        if (count == N)
            return;

        table[x][y] = 1;

        for (int i = 0; i < 4; i++) {
            if (table[x + way[i][0]][y + way[i][1]] == 0) {
                dfs(count + 1, x + way[i][0], y + way[i][1], per * way[i][2]);
                table[x + way[i][0]][y + way[i][1]] = 0;
            } else {
                answer += (per * way[i][2]) / (Math.pow(100, count + 1));
            }
        }
    }
}