[알고리즘] 백준 > #1405. 미친 로봇

문제링크

백준 #1405. 미친 로봇

풀이방법

N의 범위를 보고 완점탐색이 가능한 문제라고 생각했습니다! 그리고 가지치기가 중요하다고 생각했어요. 그래서 DFS를 사용하되, 비효율적인 경로를 차단하는 백트래킹을 사용해 문제를 해결했습니다! (비효율적인 경로 == 이미 단순하지 않은 경로)라고 생각해서 결과적으로는 (1 - 단순하지 않은 경로 확률)으로 결과를 냈습니다! 이 아이디어 말고 실제 코드는 다른 백트래킹과 다르지 않아서 따로 설명할 게 없네요 🤓

+) 이 문제는 float를 사용해 해결할 수 없습니다!
문제에 "절대/상대 오차는 10-9 까지 허용" 이런 글이 있는데요, float는 대략 6자리의 유효숫자 범위를 가지기 때문에 이 문제에서는 double을 사용해야합니다. 이 문제 뿐만 아니라 다른 상황에서도 double을 사용하는게 좋겠습니다!

코드

import java.util.*;
public class BOJ1405 {

    static int[] dy = {0, 0, 1, -1};
    static int[] dx = {1, -1, 0, 0};
    static double[] percentages = new double[4];
    static boolean[][] visited = new boolean[29][29];

    static int n;

    static public void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        for (int i = 0; i < 4; i++) percentages[i] = sc.nextDouble() / 100.0;

        visited[14][14] = true;

        double result = 1.0 - getComplicatedPathPercentage(1.0, 14, 14, 0);
        System.out.print(result);
    }

    static private double getComplicatedPathPercentage(double percentage, int y, int x, int depth) {
        double complicatedPercentage = 0.0;

        if (depth == n) return complicatedPercentage;

        for (int i = 0; i < 4; i++) {
            int nextY = y + dy[i];
            int nextX = x + dx[i];
            double nextPercentage = percentage * percentages[i];

            if (visited[nextY][nextX]) complicatedPercentage += nextPercentage;
            else {
                visited[nextY][nextX] = true;
                complicatedPercentage += getComplicatedPathPercentage(nextPercentage, nextY, nextX, depth + 1);
                visited[nextY][nextX] = false;
            }
        }

        return complicatedPercentage;
    }
}