[백준/Java] 1890번 점프

-Code

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

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

        int n = Integer.parseInt(br.readLine());

        int[][] map = new int[n][n];
        for (int row = 0; row < n; row++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int col = 0; col < n; col++) {
                map[row][col] = Integer.parseInt(st.nextToken());
            }
        }
        // dp 셋팅
        long[][] dp = new long[n][n];
        dp[0][0] = 1;
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                // 목적지 도차하면 그냥 탈출
                if (row == n - 1 && col == n - 1) {
                    break;
                }
                // 해당 위치가 갈 수 있는 위치인지
                if (dp[row][col] > 0) {
                    int moveVal = map[row][col];
                    // 다음 위치 범위 확인후 갈 수 있는 경로 갯수 추가
                    if (row + moveVal < n) {
                        dp[row + moveVal][col] += dp[row][col];
                    }
                    if (col + moveVal < n) {
                        dp[row][col + moveVal] += dp[row][col];
                    }
                }
            }
        }
        System.out.println(dp[n - 1][n - 1]);
    }
}

처음에 완전 탐색으로 재귀를 통해 접근했으나 메모리 초과로 틀렸습니다. 그래서 찾이보니 dp를 통해 푸는 문제였고 그냥 방문하는 곳만 1로 만들고 도착하면 다시 다음 위치를 1로만들고 목적지에 도착하면 1을 더해주는 방식으로 풀었습니다. 하지만 이 방식은 특정 위치에서 목적지로 가는 방법이 여러개인 경우가 배제되어서 다른 값이 나오게 되었고 그 문제는 다음 위치에 현재 위치로 갈 수 있는 갯수를 더해주면 되었습니다.