백준 1405번: 미친 로봇

https://www.acmicpc.net/problem/1405

 

로봇이 동서남북 방향으로 n번 이동할 때 각 방향으로 이동할 확률이 주어진다. 한 번 방문한 곳을 재방문하지 않을 확률을 구하는 문제이다. 

 

n<=14인 자연수 이므로 위치가 음수가 되지 않게 하기 위해 시작점 (15, 15)을 기준으로 재방문 여부를 확인하면서 DFS로 각각의 방향으로 이동한다.

private static double dfs(int x, int y, int count) {
    if (count == n) {
        return 1.0;
    }
    
    visited[x][y] = true;
    double result = 0;
    
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if (probabilities[i] == 0) {
            continue;
        }
        
        if (!visited[nx][ny]) {
            result += probabilities[i] * dfs(nx, ny, count + 1);
        }
    }
    
    visited[x][y] = false;
    return result;
}

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 미친로봇1405 {
    
    static int n;
    static double[] probabilities = new double[4];
    static boolean[][] visited = new boolean[30][30];
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 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++) {
            probabilities[i] = Double.parseDouble(st.nextToken()) / 100.0;
        }
        System.out.print(dfs(15, 15, 0));
    }
    
    private static double dfs(int x, int y, int count) {
        if (count == n) {
            return 1.0;
        }
        
        visited[x][y] = true;
        double result = 0;
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (probabilities[i] == 0) {
                continue;
            }
            
            if (!visited[nx][ny]) {
                result += probabilities[i] * dfs(nx, ny, count + 1);
            }
        }
        
        visited[x][y] = false;
        return result;
    }
}