[Java] BaekJoon 1890. 점프 (DP)(백트래킹) (실버2)

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

1890번: 점프

 

문제이해

 

목표

게임판에서, 정해진 숫자를 밟은 만큼 오른쪽이나 아래쪽으로 점프
(0,0) -> (N,N)으로 갈 수 있는 경로 수를 찾는 문제 

*주의: 0을 밟으면 이동할 수 없다. 

 

 

풀이

-> dfs 탐색
   도착 노드에 도달하면 해당 경로로 백트래킹해서 갈 수 있는 경로의 가짓수 DP를 갱신함
 

주의 

0 밟은 경우를 고려 안하면 무한히 탐색을 진행하여

StackOverFlow 오류 발생 !!

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import static java.lang.System.in;

public class Main {

    private static int[][] map;
    private static long[][] countMap;
    private static int N;

    static class Pair {
        int row, col;

        public Pair(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    static int[][] d = {{0, 1}, {1, 0}}; // 오른쪽, 아래쪽

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(in));
        N = Integer.parseInt(br.readLine());

        map = new int[N][N];
        countMap = new long[N][N];
        countMap[N - 1][N - 1] = 1;
        String[] strArr;
        for (int row = 0; row < N; row++) {
            strArr = br.readLine().split(" ");
            for (int col = 0; col < N; col++) {
                map[row][col] = Integer.parseInt(strArr[col]);
            }
        }

        // dfs 백트래킹
        dfs(0, 0);
        System.out.println(countMap[0][0]);
    }

    public static long dfs(int row, int col) {
        if (countMap[row][col] != 0) {
            return countMap[row][col];
        }

        for (int i = 0; i < 2; i++) {
            if (map[row][col] == 0) {
                break;
            }
            int tr = row + d[i][0] * map[row][col];
            int tc = col + d[i][1] * map[row][col];
            if (tr < N && tc < N && tr >= 0 && tc >= 0){
                countMap[row][col] += dfs(tr, tc);
            }
        }
        return countMap[row][col];
    }
}