[백준/JAVA] BOJ 1405 - 미친 로봇

하하... 히사시부리... 👋

👀 문제

1405번: 미친 로봇 ✨ 골드 4

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

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

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

예제 입력

2 25 25 25 25

예제 출력

0.75

🔑 키포인트

깊이 우선 탐색 수학 백트래킹

✍️ 코드

📍 백트래킹을 이용해 각 방향별 확률을 더해 주고, N번 이동한 경우 answer에 해당 확률을 더해 준다.
💡 visited 배열을 사용해 재방문 유무를 확인해 주었다.
이때, 배열 크기를 visited[2 * N + 1][2 * N + 1]로 잡아 충분한 범위를 확보해 주었다. 로봇은 [N][N]에서 시작하는 것으로 정의하고 풀었다.

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

public class BOJ1405_미친로봇 {
    static int N;
    static double e, w, s, n;
    static double[] dirProb;
    static boolean[][] visited;
    static double answer;

    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());

        dirProb = new double[4];
        e = Double.parseDouble(st.nextToken()) / 100.0;
        w = Double.parseDouble(st.nextToken()) / 100.0;
        s = Double.parseDouble(st.nextToken()) / 100.0;
        n = Double.parseDouble(st.nextToken()) / 100.0;

        dirProb[0] = e;
        dirProb[1] = w;
        dirProb[2] = s;
        dirProb[3] = n;

        visited = new boolean[2 * N + 1][2 * N + 1];
        visited[N][N] = true;
        dfs(N, N, 0, 1.0);
        System.out.println(answer);
    }

    static void dfs(int x, int y, int depth, double prob) {
        if (depth == N) {
            answer += prob;
            return;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < 2 * N + 1 && ny >= 0 && ny < 2 * N + 1) {
                if (visited[nx][ny])
                    continue;
                visited[nx][ny] = true;
                dfs(nx, ny, depth + 1, prob * dirProb[i]);
                visited[nx][ny] = false;
            }
        }
    }
}