백준 / 1520 / 내리막 길 / java

package backjun.M동적계획2;

import java.util.Scanner;

public class 내리막길 {
    static int n;
    static int m;
    static int[][] board;
    static int[][] dp;
    static int[][] dirction = {{1,0},{-1,0},{0,1},{0,-1}};

    static void dfs(int y, int x){
        if(y== m-1 & x==n-1){
            dp[y][x] = 1;
            return;
        }
        if(dp[y][x] != -1)
            return;
        
        dp[y][x] = 0;
        for(int[] d:dirction){
            int next_x = x+d[1];
            int next_y = y+d[0];

            if(next_x < n & next_x>=0 & next_y < m & next_y>=0){
                if(board[y][x] > board[next_y][next_x]){
                    dfs(next_y, next_x);
                    dp[y][x] += dp[next_y][next_x];
                }
            }
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        board = new int[m][n];
        dp = new int[m][n];

        for(int i=0; i<m;i++) {
            for(int j=0; j<n; j++){
                board[i][j] = sc.nextInt();
                dp[i][j] = -1;
            }
        }
        sc.close();

        dfs(0, 0);

        System.out.println(dp[0][0]);
    }
    
}

dp와 dfs 두 알고리즘을 통해 해결할 수 있는 문제

이 문제는 우선 갈 수 있는 모든 경로의 수를 구해야하므로 dfs 알고리즘을 통해 경로의 수를 구해야한다. 하지만 그냥 dfs로만 풀면 중복된 이미 구했던 경로에 대해 다시 방문해서 다시 dfs를 진행해나가는 불필요한 연산을 하게 된다. 이를 방지하기 위해 dp를 사용한다.

dp를 0이아닌 -1로 초기화한 이유는 연산 수행결과가 0일 수도 있기 때문이다. 0으로 초기화하면 dfs를 통해 방문한 결과가 0인지 아직 방문하지 않아서 0인지 알 수가 없게 된다. 그렇기 때문에 -1로 초기화 해준다.

이렇게 -1로 초기화한 dp를 통해 dfs 진행할 때 -1이 아니면 즉 방문한 적 있는 곳이면 return을 함으로써 중복된 dfs를 방지할 수 있다.

이렇게 dp와 dfs를 통해 정답을 구할 수 있다.