[BOJ] 백준 1405번 : 미친 로봇 (JAVA)

문제

통제 할 수 없는 미친 로봇이 평면위에 있다. 그리고 이 로봇은 N번의 행동을 취할 것이다.

각 행동에서 로봇은 4개의 방향 중에 하나를 임의로 선택한다. 그리고 그 방향으로 한 칸 이동한다.

로봇이 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 한다. (로봇이 시작하는 위치가 처음 방문한 곳이다.) 로봇의 이동 경로가 단순할 확률을 구하는 프로그램을 작성하시오. 예를 들어, EENE와 ENW는 단순하지만, ENWS와 WWWWSNE는 단순하지 않다. (E는 동, W는 서, N은 북, S는 남)

 

 

입력

첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고,  모든 확률은 100보다 작거나 같은 자연수 또는 0이다. 그리고, 동서남북으로 이동할 확률을 모두 더하면 100이다.

 

 

출력

첫째 줄에 로봇의 이동 경로가 단순할 확률을 출력한다. 절대/상대 오차는 10^-9 까지 허용한다.

 

 

풀이

전형적인 브루트포스 문제였습니다. 동서남북 방향으로 같은 지점을 방문하지 않도록 DFS를 돌리면 됩니다. 다만, 확률을 계산하는 부분을 잘 생각해야했습니다.

 

먼저, 문제의 예제에서 어떻게 0.75라는 값이 나왔는지 살펴 봅시다.

N = 2이고, 동서남북의 확률은 모두 0.25입니다. (편의상, 25 대신 0.25로 입력받는다고 가정합니다.)

그렇다면, 갈 수 있는 경우와 확률은 아래의 표와 같을 것입니다.

 

 

경우	이동 경로		확률
1	동쪽	동쪽	1/16
2	동쪽	북쪽	1/16
3	동쪽	남쪽	1/16
4	서쪽	서쪽	1/16
5	서쪽	북쪽	1/16
6	서쪽	남쪽	1/16
7	남쪽	남쪽	1/16
8	남쪽	동쪽	1/16
9	남쪽	북쪽	1/16
10	북쪽	북쪽	1/16
11	북쪽	동쪽	1/16
12	북쪽	서쪽	1/16

 

 

로봇의 이동횟수에 맞춰서 이동을 하면 위의 표와 같이 12가지 방식이 있음을 알 수 있습니다. 확률을 계산하는 방식은 간단합니다. 각 방향의 확률을 곱해가는 것이죠.

 

예를 들어, 동쪽과 남쪽을 이동할 경우, 두 개의 확률은 각각 1/₄이므로 1/₄ * 1/₄ = 1/₁₆이 된다는 것을 알 수 있습니다.

따라서, 위와 같은 방식으로 확률 모두 더하면, 12/₁₆ = 3/₄ = 0.75가 되는 것입니다.

 

이제, 우리는 로봇의 이동 경로가 단순할 확률을 일반화 할 수 있습니다. 다만, N이 최대 14라는 것을 고려하여 map의 사이즈를 29 또는 30으로 설정해 주어야 합니다.

 

아래는 확률을 구하는 전반적인 로직입니다.

 

1. 문제에서 확률을 입력받되, 0.01을 곱해서 입력받는다.

2. N이 최대 14라는 것을 고려하여 map의 사이즈를 30으로 하여 2차원 배열을 만든다.

(인덱스는 1부터 시작한다고 가정.)

3. (15, 15)을 시작점으로 잡아서 DFS를 돌린다.

(DFS의 종료 조건은 이동 횟수가 N에 도달했을 때이며, 탐색 방향은 동서남북 순서임을 유의하시길 바랍니다.)

 

아래는 위 과정을 소스코드로 작성한 것입니다.

 

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    static int[] rangeX = { 0, 0, 1, -1 };
    static int[] rangeY = { 1, -1, 0, 0 };
    static int N;
    static double[] percentages;
    static double ans = 0;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        percentages = new double[4]; // 동서남북으로 가는 각각의 확률
        for (int i = 0; i < 4; i++) {
            percentages[i] = Double.parseDouble(st.nextToken()) * 0.01;
        }
 
        boolean[][] visited = new boolean[30][30];
        visited[15][15] = true;
        DFS(15, 15, visited, 0, 1);
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
    // 동서남북으로 모든 경우에 대해 탐색.
    public static void DFS(int x, int y, boolean[][] visited, int cnt, double result) {
        if (cnt == N) { // 로봇의 최대 이동 횟수에 도달.
            ans += result; // 지금까지 이동한 방향들의 확률을 더함.
            return;
        }
 
        // 동서남북 순으로 탐색함.
        for (int i = 0; i < 4; i++) {
            int dx = x + rangeX[i];
            int dy = y + rangeY[i];
 
            if (dx <= 0 || dy <= 0 || dx >= 30 || dy >= 30) {
                continue;
            }
 
            // 특정 지점을 방문하지 않았을 경우.
            if (!visited[dx][dy]) {
                visited[dx][dy] = true;
                DFS(dx, dy, visited, cnt + 1, result * percentages[i]);
                visited[dx][dy] = false;
            }
        }
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.