문제

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

N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.

각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다.

출력
가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력한다. 경로의 개수는 263-1보다 작거나 같다.

예제 입력 1
4
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0

예제 출력 1
3

---

접근

문제가 너무 탐색 문제처럼 생겨서.... 별 고민 없이 DFS로 탐색했다가 쓴 맛을 한 번 맛보고 이게 아니라는 걸 깨달았다. 뭔가 이런 류의 문제는 보통 최단 거리로 이동하는 경로를 찾거나 최소 이동 횟수를 찾는 경우가 많아서 한 번 탐색한 위치는 다시 탐색하지 않아도 된다. 그거에 너무 익숙해져 있어서 냅다 visited 배열 생성해서 방문 여부를 저장했었음.....
하지만 이 문제는 가능한 모든 경로의 수를 다 구하는 것이기 때문에 방문 여부와는 관련이 없을뿐더러 오른쪽, 아래쪽으로만 갈 수 있기 때문에 애초에 한 번 간 곳을 다시 방문하는 일이 발생하지 않는다. 생각이라는 걸 좀 하고 문제를 풀면 이런 삽질을 안 할 텐데.

사실 이건 board[0][0] 위치에서 board[a][b] 위치에 도달하는 모든 경우의 수를 메모이제이션해가며 푸는 dp 문제였다.
항상 오른쪽이나 아래쪽으로만 이동할 수 있기 때문에 board[a][b]에 도달하기 직전 위치는 반드시 board[i][b] (i < a) 혹은 board[a][i] (i < b)일 수밖에 없다.
그러므로 i를 증가시켜가며 board[0][b] ~ board[a - 1][b] 범위와 board[a][0] ~ board[a][b - 1] 범위를 확인해보면 자신의 위치인 board[a][b]에 도달할 수 있는 모든 경우를 찾을 수 있다.
예를 들어 현재 위치가 board[3][4]이고 board[0][4]의 값이 3이라면, board[0][4] 위치에서 아래쪽으로 3만큼 이동해 현재 위치에 도달이 가능하다는 뜻이다.

이런 식으로 가능한 모든 직전 위치를 찾았다면, 그 직전 위치까지 도달 가능한 모든 경우의 수들의 총합이 현재 위치에 도달하는 경우의 수가 된다.
도착 지점인 board[N - 1][N - 1]에서 시작해 가능한 직전 위치를 하나씩 거슬러 올라가 출발 지점에 도달하면 종료하는 것이다. 따라서 이 문제는 Top-Down으로 푸는 것이 훨씬 효율적으로 보인다.
그래도 dp인 거 감 잡고 나서는 어렵지 않게 구현했다.

구현

import java.io.*;

class Main {
    static int[][] board;
    static long[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        board = new int[N][N];
        dp = new long[N][N];
        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                board[i][j] = Integer.parseInt(input[j]);
            }
        }
        System.out.println(dynamicProgramming(N - 1, N - 1));
    }

    private static long dynamicProgramming(int row, int col) {
        if ((row == 0 && col == board[0][0]) || (row == board[0][0] && col == 0)) {
            return 1;
        }

        if (dp[row][col] == 0) {
            for (int i = 0; i < row; i++) {
                if (row - i == board[i][col]) {
                    dp[row][col] += dynamicProgramming(i, col);
                }
            }
    
            for (int i = 0; i < col; i++) {
                if (col - i == board[row][i]) {
                    dp[row][col] += dynamicProgramming(row, i);
                }
            }
        }

        return dp[row][col];
    }
}

약간... 도착 지점에서 거슬러 올라간다는 점에서 1005 ACM Craft를 DP로 풀었을 때 생각이 나기도 했다. 물론 그 문제에 비하면 이건 매우매우매우매우 순한맛이지만.