[백준 1405] 미친 로봇

문제 링크 : https://www.acmicpc.net/problem/1405

이 문제는 dfs를 이용하여 풀 수 있습니다. 확률을 계산하는 문제라 접근하기 어려웠는데 확률의 속성을 알면 문제를 풀 수 있습니다.

하나의 단순한 경로로 이동했을 때의 확률은 로봇이 매 순간 이동한 확률의 곱과 같습니다. 또한 여러 경우의 수에 따른 확률의 합을 통해 전체 확률을 구할 수 있습니다. 따라서 문제에서 요구하는 정답은 로봇이 단순한 경로로 이동했을 때의 확률을 모두 더하면 됩니다.

하나의 단순한 경로로 이동했을 때의 확률을 dfs를 이용해서 구할 수 있습니다. dfs 특성 상 목적지에 도달할 때까지 하나의 경로를 탐색하므로 자신이 이전에 방문한 경로를 체크하여 방문하지 않은 경로로만 N회 이동하게 된다면 이게 곧 단순한 경로가 됩니다. 따라서 dfs로 이동한 방향의 확률을 지속해서 곱해주고 N회 이동했을 때 현재의 확률을 더해주면 정답을 구할 수 있습니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

class Main{
    static int N;
    static double res = 0;
    static int[] dy = {0,0,1,-1}, dx = {1,-1,0,0};
    static double[] p = new double[4];
    static boolean[][] check;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        check = new boolean[30][30];

        for(int i=0;i<4;i++) p[i] = ((double) Integer.parseInt(st.nextToken()) /100);

        dfs(15,15,0,1);
        System.out.println(res);
    }

    static void dfs(int y, int x, int cnt, double percent){
        if(cnt==N){
            res += percent;
            return;
        }

        check[y][x] = true;
        for(int i=0;i<4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];

            if(ny<0 || ny>=30 || nx<0 || nx>=30) continue;
            if(!check[ny][nx]){
                check[ny][nx] = true;
                dfs(ny,nx,cnt+1,percent * p[i]);
                check[ny][nx] = false;
            }
        }
    }

    static class Robot{
        int y;
        int x;
        int cnt;
        double p;

        Robot(int y, int x, int cnt, double p){
            this.y = y;
            this.x = x;
            this.cnt = cnt;
            this.p = p;
        }
    }
}