[BOJ] 백준 1890 점프

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

 Input 

4

2 3 3 1

1 2 1 3

1 2 3 1

3 1 1 0

 

 Output 

3

▶ 동적계획법(Dynamic Programming, DP) 

동적계획법(Dynamic Programming, DP)

[이동 방식]　

- 아래쪽 혹은 오른쪽으로 이동할 수 있습니다.

- 이동거리는 각 칸에 적혀있는 숫자만큼 이동해야 합니다.

 

[구현]

이동 거리와 방향 특성을 이용.

dp[i][j] = 해당 지점에 도달(방문)될 수 있는 모든 경로수

[Test Case 분석]

---

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
class Vertex{
    int x, y;
    int point;
     
    public Vertex(int x, int y, int p) {
        this.x = x;
        this.y = y;
        point = p;
    }
}
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        int N = Integer.parseInt(sc.next());
         
        int[][] arr = new int[N+1][N+1];
        long[][] dp = new long[N+1][N+1];
         
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                arr[i][j] = Integer.parseInt(sc.next());
            }
        }
         
        dp[1][1] = 1;
         
        int[] rowMove = {0, 0};
        int[] colMove = {0, 0};
         
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(dp[i][j] > 0 && !(i==N && j==N)) {
                    rowMove[1] = arr[i][j];
                    colMove[0] = arr[i][j];
                     
                    for(int k=0; k<2; k++) {
                         
                        int next_x = i + rowMove[k];
                        int next_y = j + colMove[k];
                         
                        if(next_x > 0 && next_y > 0 && next_x <= N && next_y <= N) {
                            dp[next_x][next_y] += dp[i][j];
                        }
                    }
                }
            }
        }
        // 정답 출력
        System.out.println(dp[N][N]);
    }
}