1405_미친로봇 (Java)

문제

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

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

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

입력

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

확률의 단위는 %이다.

출력

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

예제 입력 1

2 25 25 25 25

예제 출력 1

0.75

예제 입력 2

1 25 25 25 25

예제 출력 2

1.0

예제 입력 3

7 50 0 0 50

예제 출력 3

1.0

예제 입력 4

14 50 50 0 0

예제 출력 4

0.0001220703125

예제 입력 5

14 25 25 25 25

예제 출력 5

0.008845493197441101

아이디어

• 좌표도 없이 이동만 달랑 하고, 이동할 확률도 제각각이라 초반엔 어떻게 좌표를 설정해야할지 고민했었다. 문제에서 이동횟수가 최대 14회 이동이라고 하였고, 그래서 배열을 30x30크기로 직접 설정하여 중앙에서 설정하면 되겠거니 하고 배열을 생성하였다.
• 배열을 30x30으로 생성한 이유는, 그래야 도중에 모서리에 겹치지 않고 이동하여 모든 확률이 다 나올 수 있어서이다. (벽에 부딪혀서 강제로 dfs가 종료되는 상황이 발생하는 것을 방지)
• 이후에는 사방 탐색을 실시하고 check되지 않은 좌표에 한해 탐색을 실시하고, 탐색할 때 마다 각자의 방향에 대한 확률을 곱해주면서 dfs를 끝까지 진행하였고, 마지막에 확률을 출력하도록 하였다.
• 처음 문제를 풀었을 때, 출력 형식이 지수표현식으로 나왔기 때문에 BigDecimal을 통해 지수표현 대신 전체 숫자를 표현할 수 있도록 수정해주었다.

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.util.Random;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static double[] percentage;
    static boolean[][] check; // 로봇방향 체크용...
    static int[] dr = new int[] { -1, 1, 0, 0 };
    static int[] dc = new int[] { 0, 0, -1, 1 };
    static double sum;

    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());
        percentage = new double[4];
        check = new boolean[30][30];
        sum = 0;
        for (int i = 0; i < 4; i++) {
            percentage[i] = Integer.parseInt(st.nextToken()) * 0.01; // 확률

        }

        dfs(15, 15, 1, 0); // 중앙에서 시작할게, 움직이면 시작

        BigDecimal bigDecimal = new BigDecimal(sum);

        System.out.println(bigDecimal.toString());

    }

    public static void dfs(int r, int c, double percent, int cnt) {
        if (cnt == N) {
            sum += percent;
            return;
        }
        check[r][c] = true;
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d]; // 여기서 이탈할일은 절대없다
            if (nr >= 0 && nr < 30 && nc >= 0 && nc < 30) { // 범위 내
                if (!check[nr][nc]) {// 방문한적 없으면.
                    check[nr][nc] = true;
                    dfs(nr, nc, percent * percentage[d], cnt + 1); // 한번 재실행~
                    check[nr][nc] = false;
                }
            }
        }

    }

}

결과