[BOJ] 경로 찾기 - 1513

🎨 문제

1513번: 경로 찾기

📘 풀이

이 문제는 DP로 풀 수 있습니다. 만약 완전 탐색을 할 경우 거쳐가는 오락실의 개수의 경우의 수(0~50)만큼 학원을 가는 경우의 수를 완전탐색으로 구하게 됩니다. 1,000,0007로 나누는 것을 보면 경우의 수가 아주 커서 이 방법은 옳지 않음을 짐작할 수 있습니다. 따라서 이동 경로를 기억하여 다음 연산에 사용하도록 합시다.

 

DP문제 풀이의 중요한 포인트는 점화식도 있지만, 상태값도 중요합니다. 점화식은 특정 상태에서의 최적값을 구하는 식입니다. 즉, 우리는 어떤 상태를 통해 최적값을 구할지 정해야 합니다.

 

문제의 조건을 통해 상태값을 추려보겠습니다. 현재 세준의 위치가 주어지고, 오락실은 오름차순으로 방문해야합니다. 그리고 오락실에 총 방문한 횟수도 알아야 합니다. 이 네 가지 값을 기준으로 상태값을 정하겠습니다.

int[][][][] DP = new int[행][열][이전_오락실_번호][남은_오락실_방문_횟수];

배열의 크기는 문제 조건에 의해 51 x 51 x 51 x 51이 됩니다.

 

배열의 초기값은 0입니다. 하지만 0도 정답이 될 수 있습니다.

ex) 오락실을 0번 방문하고 (N, M)까지 도달하는 경우의 수가 0

따라서 배열을 -1로 초기화 해줍니다.(정답이 될 수 없는 값이면 됩니다.)

for (int i = 0; i < DP.length; i++) {
    for (int j = 0; j < DP[0].length; j++) {
        for (int k = 0; k < DP[0][0].length; k++) {
            Arrays.fill(DP[i][j][k], -1);
        }
    }
}

특정 상태에서의 최적해를 구하는 함수를 만듭니다. 저는 Top-Down 형식으로 재귀를 활용해 문제를 풀었습니다. 이 방법이 완전 탐색 방법과 비슷해 이해하기 편합니다.

// MAP에는 일단 길(0)과 오락실 번호가 저장되어 있습니다.
private static int solve(int r, int c, int prevC, int visitC) {

    if (visitC < 0) return 0;
    if (r > N || c > M) return 0;
    if (r == N && c == M) {
        if (visitC == 0 && MAP[r][c] == 0) return 1;
        if (visitC == 1 && MAP[r][c] > prevC) return 1;
        return 0;
    }

    if (DP[r][c][prevC][visitC] != -1) return DP[r][c][prevC][visitC];

    int result;

    if (MAP[r][c] == 0) {
        result = (solve(r + 1, c, prevC, visitC) + solve(r, c + 1, prevC, visitC)) % DIV;
        return DP[r][c][prevC][visitC] = result;
    }

    if (MAP[r][c] > prevC) {
        result = (solve(r + 1, c, MAP[r][c], visitC - 1) + solve(r, c + 1, MAP[r][c], visitC - 1)) % DIV;
        return DP[r][c][prevC][visitC] = result;
    }

    return DP[r][c][prevC][visitC] = 0;
}

마지막으로 해당 함수를 오락실을 몇 번 경유하는지에 대한 경우의 수만큼 반복해줍니다.

StringBuilder sb = new StringBuilder();
for (int i = 0; i <= C; i++) {
    sb.append(solve(1, 1, 0, i)).append(" ");
}

System.out.println(sb);

📗 코드

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

import static java.lang.System.in;

// 경로 찾기
public class Main {

    private static final int DIV = 1_000_007;

    static int N, M, C;
    static int[][] MAP = new int[51][51];
    static int[][][][] DP = new int[51][51][51][51];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        int[] input = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        N = input[0];
        M = input[1];
        C = input[2];

        for (int i = 1; i <= C; i++) {
            input = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
            MAP[input[0]][input[1]] = i;
        }

        for (int i = 0; i < DP.length; i++) {
            for (int j = 0; j < DP[0].length; j++) {
                for (int k = 0; k < DP[0][0].length; k++) {
                    Arrays.fill(DP[i][j][k], -1);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i <= C; i++) {
            sb.append(solve(1, 1, 0, i)).append(" ");
        }

        System.out.println(sb);
    }

    private static int solve(int r, int c, int prevC, int visitC) {

        if (visitC < 0) return 0;
        if (r > N || c > M) return 0;
        if (r == N && c == M) {
            if (visitC == 0 && MAP[r][c] == 0) return 1;
            if (visitC == 1 && MAP[r][c] > prevC) return 1;
            return 0;
        }

        if (DP[r][c][prevC][visitC] != -1) return DP[r][c][prevC][visitC];

        int result;

        if (MAP[r][c] == 0) {
            result = (solve(r + 1, c, prevC, visitC) + solve(r, c + 1, prevC, visitC)) % DIV;
            return DP[r][c][prevC][visitC] = result;
        }

        if (MAP[r][c] > prevC) {
            result = (solve(r + 1, c, MAP[r][c], visitC - 1) + solve(r, c + 1, MAP[r][c], visitC - 1)) % DIV;
            return DP[r][c][prevC][visitC] = result;
        }

        return DP[r][c][prevC][visitC] = 0;
    }
}