백준 1890 (점프)

문제

1890번: 점프

N * N의 2차원 배열이 있으면 arr[0][0] 부터 시작해서 현재 위치한 값에 해당하는 만큼 오른쪽 과 아래로 점프할 수 있다.

이 때 arr[N-1][N-1]로 도달 할 수 있는 경우의 수를 구하는 문제이다.

예를 들어  그림 1과 같은 상황이 주어진다면

정답은 3이다.

---

먼저 dp식을 세울 수 있었다.

dp[i][j] = x

arr[i][j]에 도달할 수 있는 경우의 수는 x 개이다.

점화식을 세우는것은 어렵지 않았지만, 현재 위치에서 칸에 해당하는 만큼 오른쪽, 아래쪽으로 이동하는데 고민이 있었다.

 

처음에는 BFS를 활용했다.

하지만 메모리 초과가 나왔다.

아마도 최악의 경우 여러 위치가 큐에 저장되므로 메모리 초과가 나올 것이다.

 

그러면 어떻게 현재 위치에서 오른쪽, 아래쪽을 이동할 것인가??

 

정답은 그냥 단순히 2차원 배열을 순회하면서 현재 위치의 값만큼 이동한 dp에 값을 저장하는 것이다.

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

                int go = (int) arr[i][j];
                if(i+go <n){
                    dp[i+go][j] += dp[i][j];
                }

                if(j + go < n){
                    dp[i][j+go]+= dp[i][j];
                }

            }
        }

우리는 지나가지 않는 칸에대해서는 무시해도 된다. 따라서 dp[i][j] = 0 이면 걍 무시하면 되는 것이다.

또한 i = n-1 , j = n-1 이면 마지막 끝칸에 온것이므로 종료해준다.

 

그 다음 현재 위치의 값만큼 오른쪽, 아래쪽으로 이동할 수 있다면 현재 위치의 경우의 수만큼 이동할 위치에 더해주었다.

---

전체 코드이다.

public class Main {
    private static long[][]arr;
    private static long[][]dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        arr = new long[n][n];
        dp = new long[n][n];


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

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

                int go = (int) arr[i][j];
                if(i+go <n){
                    dp[i+go][j] += dp[i][j];
                }

                if(j + go < n){
                    dp[i][j+go]+= dp[i][j];
                }

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

    }
}