[AlgoSpot] 두니발 박사의 탈옥

문제 설명

알고리즘 문제 해결 전략 - 동적 계획법
https://algospot.com/judge/problem/read/NUMB3RS

문제 풀이

• 동적 계획법 문제이다.

• 우선 완전 탐색으로 접근하기 위해 가능한 모든 경우의 수를 계산하는 방법을 고려해보면 아래와 같은 발상을 할 수 있다.

  solve(int[] path) = q에 도달하는 모든 경로의 확률을 더해서 출력함.

• 하지만 위와 같은 발상으로는 메모이제이션이 불가하다. 항상 동적 계획법을 고려할 때 메모이제이션을 활용하기 위해서는 부분문제가 그 시점 이후의 인자들을 토대로 결과를 만들어야 함을 생각해야 한다. 따라서 위의 조건을 적용하여 함수를 다시 정의하면

  solve(here, days) = 박사가 days일째에 here에 있을 때, 마지막 날에 q에 있을 조건부 확률 반환.

• 위와 같이 설계하면 dp[here][days] 형태로 메모이제이션이 가능하다.

• 자세한 구현은 소스 참조.

소스 코드 (JAVA)

import java.util.Scanner;

public class Main {
    public static int C, N, D, P, T, Q;
    public static int adj[][] = new int[50][50];        //adj : 각 마을의 연결 여부
    public static int deg[] = new int[50];              //deg : 각 마을에 연결된 마을 갯수
    public static double dp[][] = new double[50][100];  //dp[here][days] : here 위치에 days 일 뒤에 있을 때 마지막에 Q에 있을 확률

    public static void initDeg() {
        for (int i = 0; i < N; i++)
            deg[i] = 0;
    }

    public static void initDp() {
        for (int i = 0; i < N; i++)
            for (int j = 0; j < D; j++)
                dp[i][j] = -1.0;
    }

    public static double solve(int here, int days) {
        //기저 조건 : 마지막 날일 때 
        if (days == D) {
            if (here == Q) return 1;
            else return 0;
        }
        if (dp[here][days] != -1.0) return dp[here][days];
        double result = 0.0;
        for (int i = 0; i < N; i++) {
            if (adj[here][i] == 0) continue;
            result += solve(i, days + 1) / deg[here];
        }
        dp[here][days] = result;
        return result;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        C = sc.nextInt();
        for (int c = 0; c < C; c++) {
            N = sc.nextInt(); D = sc.nextInt(); P = sc.nextInt();
            initDeg();
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    adj[i][j] = sc.nextInt();
                    if (adj[i][j] == 1) deg[i]++;
                }
            }
            T = sc.nextInt();
            for (int t = 0; t < T; t++) {
                Q = sc.nextInt();
                initDp();
                System.out.println(solve(P, 0));
            }
        }
    }
}