[백준]1405: 미친 로봇 - JAVA

[백준]1405: 미친 로봇

www.acmicpc.net/problem/1405

1405번: 미친 로봇

풀이

DFS + 백트래킹을 사용하여 풀었다.

 

결국엔 문제에서 구하는 값은 같은 곳을 방문하지 않고 N번동안 이동할 때의 확률을 구하는 것이다. 즉 DFS를 사용하여 N번만큼 이동하되 visited 함수를 사용하여 같은 공간은 방문하지 않도록 처리하면 된다.

 

이때 이동할 확률을 구하는 방법은 같은 공간을 방문하지 않고 이동하며, 이동할 때매다 이동할 방향의 확률을 곱해서 그 값을 모두 더해주면 된다.

 

예를들어 N이 2이고 동 서 남 북으로 이동할 확률이 각각 25라고 할때 동 -> 동으로 이동할 확률은 다음과 같다.

동 -> 동 = 25(동) * 25(동)이 된다. 

 

즉, DFS로 한 방향으로 계속 방문하되, 이전에 방문한 곳은 방문하지 않으며 해당 방향으로 이동할 때 그 방향의 확률을 곱해주고 N번 이동이 끝나면 그 값을 결과값에 더해주면 된다.

 

이때 N의 최대값은 15이다. 그러므로 시작지점을 15, 15로 잡고 최소 좌표값을 0, 0/ 최대 좌표값을 30, 30으로 설정해주었다.

 

코드

import java.util.*;
 
public class Main {    
    
    static int[] dx = {0, 0, 1, -1}; //동 서 남 북 순서
    static int[] dy = {1, -1, 0, 0};
    static double[] percent;
    static boolean[][] visited;
    static double result;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        
        percent = new double[4];
        for(int i = 0; i < 4; i++) {
            percent[i] = scan.nextInt() * 0.01;
        }
        
        visited = new boolean[30][30]; //시작점을 15, 15로 잡기 위함.
        result = 0;
        dfs(15, 15, 0, n, 1);
        System.out.println(result);
    }    
    
    public static void dfs(int x, int y, int idx, int n, double total) {
        if(idx == n) {
            result += total;
            return;
        }
        
        visited[x][y] = true;
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx >= 0 && ny >= 0 && nx < 30 && ny < 30) {
                if(visited[nx][ny] == false) {
                    visited[nx][ny] = true;
                    dfs(nx, ny, idx + 1, n, total * percent[i]);
                    visited[nx][ny] = false;
                }
            }
        }
    }
}