[Java][DFS][BOJ] 1405번 미친 로봇

1405번 미친 로봇

🤔 문제 이해하기

• 로봇은 사방으로 이동할 수 있으며 각 방향을 이동할 확률이 주어진다.

• 로봇이 총 n번 이동한다.

• 이미 방문한 경로에 또 방문하는 경우를 단순하지 않은 경로, 그렇지 않은 경로를 단순한 경로라고 한다.

• 로봇이 단순한 경로로 이동할 확률을 구해라

• n ≤ 14

⭐ 알고리즘

• DFS
• 백트래킹

📖 스토리 라인

1. 30 x 30 크기의 공간이 있고, 해당 로봇은 15행 15열에서 출발한다.
2. dfs로 방문여부를 표시하며 진행한다.
   • 임의의 경로로 이동할 때 다음 방향을 선택할 확률은 지금까지 이동한 확률 * 다음 방향으로 이동할 확률이다.
   • 코드의 move() 호출 부분을 부분에 나와있다.
3. 방문한 곳에 다시 방문하다면 되돌아온다. (백트래킹)
4. 목표한 횟수만큼 이동했다면 단순한 경로이므로 해당 경로로 이동할 확률을 더한다.

💻 문제를 해결한 코드

import java.io.*;
import java.util.*;

public class Main {

    static int n;
    static double ans = 0;
    static double[] p = new double[4]; // E(동), W(서), S(남), N(북)쪽으로 이동할 확률
    static int[] dr = {0, 0, 1, -1};
    static int[] dc = {1, -1, 0, 0};

    static boolean[][] visited = new boolean[30][30];

    // 백트래킹으로 모든 경로를 이동해보며 단순한 경로인지 확인
    // move: 지금까지 움직인 횟수, cr: 현재 있는 행, cc: 현재 있는 열
    private static void move(int move, int cr, int cc, double per) {
        if (move == n) { // n번 만큼 이동한 경우
            ans += per;
            return;
        }

        for (int dir = 0; dir < 4; ++dir) {
            int nr = cr + dr[dir];
            int nc = cc + dc[dir];

            if (visited[nr][nc]) continue; // 이미 방문한 곳인 경우

            visited[nr][nc] = true;
            move(move + 1, nr, nc, per * p[dir]);
            visited[nr][nc] = false;
        }
    }

    // 변수 입력 받기
    private static void readData() throws Exception{
        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) {
            p[i] = Integer.parseInt(st.nextToken()) * 0.01;
        }

        br.close();
    }

    // 데이터 쓰기
    private static void writeData() throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        sb.append(ans).append("\n");

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    public static void main(String[] args) throws Exception {
        readData();
        visited[15][15] = true;
        move(0, 15, 15, 1);
        writeData();
    }
}

❗ 주의할 점

각 방향으로 이동할 확률을 나타내는 변수 (double[] p)를 입력받을 때
p[i] = Integer.parseInt(st.nextToken()) / 100; 을 썼더니 모든 확률이 0.0으로 저장됐다.

1. int / int 연산
2. double로 casting 되는데
   1번 과정에서 0이라는 결과가 도출되기 때문이었다.

따라서 int * double로 연산하여 의도한 값이 저장되도록 변경하여 문제를 해결할 수 있었다.