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

문제

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

---

풀이(25분)

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

public class Main {

    static int n;
    static double answer;
    static double[] directionProbability = new double[4];
    static int[] dx = {0, 0, 1, -1}; // 동, 서, 남, 북 이동 기준
    static int[] dy = {1, -1, 0, 0}; // 동, 서, 남, 북 이동 기준
    static boolean[][] visited = new boolean[29][29]; // 방문 체크 배열

    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());
        int E = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        // 이동 확률 저장 (백분율 → 소수 변환)
        directionProbability[0] = E / 100.0;
        directionProbability[1] = W / 100.0;
        directionProbability[2] = S / 100.0;
        directionProbability[3] = N / 100.0;

        // 시작 위치 (14,14) 방문 체크 후 DFS 탐색 시작
        visited[14][14] = true;
        dfs(14, 14, 0, 1.0); // x, y, 현재 깊이, 현재 확률

        // 정답 출력 (소수점 9자리까지)
        System.out.printf("%.9f", answer);
    }

    static void dfs(int x, int y, int depth, double probability) {
        // 종료 조건: 최대 이동 횟수 도달
        if (depth == n) {
            answer += probability;
            return;
        }

        // 4방향 탐색 (동, 서, 남, 북)
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (!visited[nx][ny] && directionProbability[i] > 0) { // 방문하지 않았고 확률이 0이 아닐 때만 이동
                visited[nx][ny] = true; // 방문 체크
                dfs(nx, ny, depth + 1, probability * directionProbability[i]);
                visited[nx][ny] = false; // 백트래킹 (원상 복구)
            }
        }
    }
}

---

문제 풀이 전략

 

dfs와 백트래킹을 통해 정답을 추적해 나가는 방식이다.

 

골드 4 수준의 문제를 접하는 사람에게 어렵지 않은 dfs+백트래킹이라고 생각한다.

 

다만 중요한 부분은 소수점을 매번 추적해 나가며, 정답을 작성하는 것이다.

또한 문제를 정확히 분석하고, 좌우방향의 제한이 없다는 것과 14번의 이동이 최대라는 점에서 총 29x29의 이차원 배열을 만드는 것이다.

이를 통해 시작점을 가운데 위치시키고, 문제를 해결할 수 있다.