[BOJ/JAVA] 1890. 점프

AmeriKano·2023년 4월 3일

문제 링크

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

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

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

입력

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

출력

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

입력 예시

출력 예시

접근 방법

다이나믹 프로그래밍 문제인 건 알고 있었지만 혹시나 재귀적인 탐색으로도 가능할까 해서 처음엔 재귀로 풀어봤는데 당연히 시간초과였다. 그래서 얌전히 다이나믹 프로그래밍으로 풀었다. 아이디어는 다음과 같다.
게임판과 같은 크기의 배열을 선언한 뒤, (0, 0) 에서부터 시작해 (무조건 가장 왼쪽 위 칸에서 시작하기 때문에 1로 초기화해둔다.) 다른 칸으로 이동 가능한 경우의 방문 수를 누적한다. 방문 수를 누적한다고 표현한 이유는, 시작점이 아닐 때 이 점까지 도달할 수 있는 총 경우의 수가 이 새로운 배열에 저장되어 있을 것이기 때문이다. 이를 그림으로 표현하면 다음과 같다.

이 과정을 마지막 점에 도착할 때까지 반복해 주면 최대 100*100 번의 연산만으로 전체 경우의 수를 구할 수 있게 된다.

소스 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[][] gameBoard = new int[n][n];
        long[][] dp = new long[n][n];

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

        dp[0][0] = 1;
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                int d = gameBoard[i][j];
                if (d==0) break;
                if(i+d < n) dp[i+d][j] += dp[i][j];
                if(j+d < n) dp[i][j+d] += dp[i][j];
            }
        }

        System.out.println(dp[n-1][n-1]);
    }
}