백트래킹. 미친 로봇

문제

로봇이 N번만큼 행동하고, N 길이의 문자열 형태로 명령이 주어진다. 이 문제는 로봇이 같은곳을 중복방문하는지 체크하면되는 문제이다.

해결방향성

로봇은 동,서,남,북으로 갈수있기때문에, N번만큼 행동했을때, E를 N번만큼 갈수도있다. 따라서 나는 로봇을 (N,N)에 위치시키고, 사방으로 2Nx2N 이차원배열을 만들어 명령에 따라 이동하면서 로봇이 중복방문하면 해당 명령을 포함하지않는 방식으로 하였다. 일단 명령은 4가지중에서 하나의 명령을 택하고, N개의 명령을 하기때문에 중복순열이다. 따라서 방향은 중복순열로 가져갔다. 하지만 문제는 확률 계산인데, 확률 계산을 명령을 모두 실행한 후 계산하면 안된다. 그러면 percent수를 너무 많이 계산하기때문에 overflow가 나는듯하다. 따라서 매개변수에 대입해 재귀를 돌때마다 계산하는 방식으로 하고, 해당하는 경우에만 totalPercent에 더해주는 방식으로 했다. 또한, 중간에 visited 검사를 하는것을 통해서 약간의 프루닝을 추가하는것도 좋다. 아마 메모리 초과가 이전에 여기서 난듯하다. 이미 다 계산하고 해당하는지 검사하는거랑, dfs 돌릴때 방문했던 점 검사를 하고, 해당하는 경우만 카운트하는거랑은 매우 차이나기 때문이다.

코드

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

public class Main {
    static int N;
    static int[] percent;

    // 이문제는 계산을 한다음에 한꺼번에 계산 x -> dfs 이동하면서 계산 o
    public static void main(String[] args) throws IOException {
        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()); // 14이하
        percent = new int[4];
        for (int i = 0; i < 4; i++) {
            percent[i] = Integer.parseInt(st.nextToken()); // 자연수, 0이상 100이하
        }

        visited = new boolean[2 * N + 1][2 * N + 1]; // 좌표 0 ~ 2N까지
        visited[N][N] = true;

        dfs(N, N, 0, 1.0);

        bw.write(String.valueOf(totalPercent));

        bw.flush();
        br.close();
        bw.close();
    }
    private static double totalPercent = 0.0;
    static boolean[][] visited;
    static int[] dr = {0, 0, 1, -1};
    static int[] dc = {1, -1, 0, 0};
    private static void dfs(int r, int c, int cnt, double per) {
        if (cnt == N) {
            // 총 퍼센티지 모두 구함.
            totalPercent += per;
            return;
        }
        for (int i = 0; i < 4; i++) {
            // 동서남북
            int nr = r + dr[i];
            int nc = c + dc[i];

            // 방문했던점이면
            if (visited[nr][nc]) continue;

            visited[nr][nc] = true;
            dfs(nr, nc, cnt + 1, per * (percent[i] / 100.0));
            visited[nr][nc] = false;
        }
    }
}

결론

percent는 매개변수로 곱하면서 재귀를 들어간다.