모든 경로를 확인하면서 백트레킹으로 단순하지 않은 경로를 찾아주었다.
자바에 지수형 표현을 제거하기 위해 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));
}
}
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
감소하는 수 - 1038번 (0) | 2021.11.25 |
---|---|
리모컨 - 1107번 (0) | 2021.11.23 |
음식 평론가 - 1188번 (0) | 2021.11.22 |
공약수 - 2436번 (0) | 2021.11.16 |
수고르기 - 2230번 (0) | 2021.11.16 |