[백준] 1520 내리막 길 [java]

문제

https://www.acmicpc.net/problem/1520

풀이 방법

dp 배열 "현재 위치까지 오는 경우의 수" 를 저장하기로 하고
현재 위치에서 갈 수 있는 위치를 탐색하며 dp 배열을 갱신하려 했는데,
생각해보니까 이미 탐색한 위치를 다시 탐색을 안하는 것도 아니기 때문에 시간 초과가 날 것으로 예상하였다.
풀이 방법은
dp 배열에 "현재 위치에서 row-1, col-1까지 이동하는 경우의 수" 를 저장하는 것이다.

동작

예제에서 보면,

처음에 arr[0][0]에서 분기하여 45 방향으로 탐색한다.
북남동서 순서로 탐색할 때, 처음 탐색에서 이렇게 된다.

arr[0][3]의 32에서 30와 20으로 분기되기 때문에 이런 모양이다.

그리고 처음에 arr[0][0]에서 분기된 30을 탐색한다.


dp[0][0]이 정답이다

코드

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

// 내리막길로 갈 수 잇는 경우의 수
// 각 칸에 현재까지 온 방법의 수 적기
public class Main {

    public static int[] dirX = {0, 1, 0, -1};
    public static int[] dirY = {-1, 0, 1, 0};

    public static int DFS(int[][] dp, int[][] arr, int currX, int currY){

        if(dp[currY][currX] != -1) return dp[currY][currX];

        if(currX == arr[0].length - 1 && currY == arr.length - 1) return 1;

        dp[currY][currX] = 0;

        for(int i = 0; i < 4; i++){
            int nextX = currX + dirX[i];
            int nextY = currY + dirY[i];

            if((nextX < 0 || nextX >= arr[0].length) || (nextY < 0 || nextY >= arr.length)) continue;

            if(arr[nextY][nextX] < arr[currY][currX]){

                dp[currY][currX] += DFS(dp, arr, nextX, nextY);
            }
        }

        return dp[currY][currX];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int row = Integer.parseInt(stringTokenizer.nextToken());
        int col = Integer.parseInt(stringTokenizer.nextToken());
        int[][] arr = new int[row][col];
        int[][] dp = new int[row][col];
        for(int i = 0; i < row; i++){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for(int j = 0; j < col; j++){
                arr[i][j] = Integer.parseInt(stringTokenizer.nextToken());
                dp[i][j] = -1;
            }
        }


        int ans = DFS(dp, arr, 0, 0);
        
        System.out.println(ans);
        
    }
}