[BOJ] 백준 [1890] 점프 JAVA

문제

풀이

1. 이 문제는 bfs와 같은 일반적인 그래프 탐색으로 접근하면 시간초과가 나버린다.. -> dp 문제

2. 경로의 개수는 263-1보다 작거나 같으므로 dp의 자료형을 long으로 선언

 

 

import java.util.*;
import java.io.*;
 
public class Main{
 
    static int N;
    static int[][] map;
    static long[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N+1][N+1];
        dp = new long[N+1][N+1];
        for(int i=1;i<=N;i++){
            String[] input = br.readLine().split(" ");
            for(int j=1;j<=N;j++)
                map[i][j] = Integer.parseInt(input[j-1]);
        }
        dp[1][1] = 1;
        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                if(i==N&&j==N) //도착지점
                    continue;
                int next = map[i][j]; //map 값
                if(i+next <= N)
                    dp[i+next][j] += dp[i][j]; //세로 이동
                if(j+next <= N)
                    dp[i][j+next] += dp[i][j]; //가로 이동
            }
        }
        System.out.println(dp[N][N]);
    }
 
}
 

풀어보니 일반적인 탐색 방식으론 절대 안풀린다 .. 메모리or시간초과 발생함. 그래프 탐색을 주로 풀어본 나에겐 어려운 문제였다 ..