[BOJ] 1890. 점프 - JAVA 자바

1890번: 점프

💡 DP (Top-Down)

 

오른쪽 방향 또는 아래 방향으로 탐색하며 도착지점까지 가는 경로의 개수를 찾는 문제로 처음은 DFS로 해결하였지만 시간초과로 인해 DP를 활용하여 특정 경로에서 도착지점까지 가는 경로 개수를 저장해두고 방문한 경로이면 저장한 경로 개수를 return하며 해결할 수 있었다.

 

DFS로 구현했을 때 시간초과가 난다면 DP 로 해결하기

 

해당 좌표에서 도착지점까지 가는 경로의 개수가 0인 좌표와 처음 방문하는 좌표를 구분하기 위해 각 좌표마다 경로의 개수를 저장하는 이차원 배열인 dp의 값들을 모두 -1로 초기화하였다.

 

이후 DFS 구조를 활용하여 도착지점에 도착한 경우에는 하나의 경로를 찾은 것이므로 1을 return 하고 처음 방문한 구역이면 오른쪽 or 아래쪽으로 탐색하며 재귀호출을 한다. (x,y) 좌표에서 도착지점까지 가는 경로의 개수를 추가하며 탐색을 진행하는 과정에서 경로의 중복을 방지한다.

 

방문한 구역이면 dp에 저장된 해당 좌표의 경로의 개수를 return 한다.

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

public class Main {
    static int N;
    static int[][] board;
    static long[][] dp;
    static int[] distX = { 1, 0};
    static int[] distY = { 0, 1};

    public long solution(int x, int y) {
        // 도착한 경우
        if (x == N-1 && y == N-1) {
            return 1;
        }
		
        // 처음 방문하는 좌표인 경우
        if(dp[x][y] == -1) {
            dp[x][y] = 0;
            for(int i=0;i<2;i++) {
                int dx = x + distX[i] * board[x][y];
                int dy = y + distY[i] * board[x][y];

                if(dx < N && dy < N) {
                    dp[x][y] += solution(dx, dy);
                }
            }
        }
        return dp[x][y];
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        Main M = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        board = new int[N][N];
        dp = new long[N][N];

        for(long[] col : dp) {
            Arrays.fill(col, -1);
        }

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 시작은 0,0 칸. 도착은 N-1,N-1 칸         
        M.solution(0, 0);
        System.out.println(dp[0][0]);
    }
}

---