백준 1890번 점프 :: 마이구미

이번 글은 백준 알고리즘 문제 1890번 "점프" 를 다뤄본다.

본인의 실력으로는 BFS, DFS 둘 다 시도해봤지만 도저히 맞을 수가 없었다.

그리하여 동적계획법으로 문제를 접근했다.

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

각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다.

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

각 칸을 기준으로 거리를 통해 갈 수 있는 지점에 경로의 개수를 업데이트 해나간다.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        int dist = map[i][j];
        int down = dist + i;
        int right = dist + j;
        // 아래
        if (down < n) {
            dp[down][j] += dp[i][j];
        }
        // 오른쪽
        if (right < n) {
            dp[i][right] += dp[i][j];
        }
    }
}

사실상 모든 칸을 완벽히 돌 필요는 없다.

거를 수 있는 건 거르면 된다.

예를 들어, (1, 1)에서 오른쪽으로 3칸 이동하면 (1, 4) 가 된다.

(1, 2), (1, 3) 은 사실상 어떠한 경우라도 필요 없는 칸이 된다. (오른쪽과 아래쪽만 거리값을 통해 이동하기 때문)

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (dp[i][j] == 0 || (i == n - 1 && j == n - 1)) {
            continue;
        }
        // ...........
    }
}

1. dp[i][j] == 0 

=> 위에서 말한 거르는 경우

2. i == n - 1 && j == n - 1

=> 마지막 도착 지점에서는 더이상 이동할 필요가 없다.

private void solve() {
    int[][] map = new int[101][101];
    long[][] dp = new long[101][101];
    int n = sc.nextInt();
 
    dp[0][0] = 1;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            map[i][j] = sc.nextInt();
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dp[i][j] == 0 || (i == n - 1 && j == n - 1)) {
                continue;
            }
 
            int dist = map[i][j];
            int down = dist + i;
            int right = dist + j;
 
            if (down < n) {
                dp[down][j] += dp[i][j];
            }
 
            if (right < n) {
                dp[i][right] += dp[i][j];
            }
        }
    }
    System.out.println(dp[n - 1][n - 1]);
}