문제

백준 1520번: 내리막 길

접근법

올바른 접근법

• DP 배열에 특정 위치에서 목적지까지 도달할 수 있는 경우의 수를 저장해야 한다.
• DP의 값이 초기 값 -1이 아니라면(이미 계산된 경로)라면 바로 반환하여 연산 횟수를 줄인다.
• DFS 메소드의 반환값으로 특정 위치에서 목적지까지의 경로 경우의 수를 반환함으로써 DP에 저장된 값이 목적지까지 이어진 경우의 수를 보장한다.

DP 배열의 모습

나의 접근 실수

• DP의 값에 해당 위치까지의 도달하는 경우의 수를 저장하는 방식으로 접근했었다. 그 결과, 목적지까지 이어지지 않은 경우에도 DP에 값을 기록하여서 목적지까지 이어지는 경로만 찾아내는 것이 불가능하였다.

코드

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

public class PN1520 {
    static int M;
    static int N;
    static  int[][] map;
    static int[][] dp;
    static final int[] DIR_Y = {1, 0, -1, 0};
    static final int[] DIR_X = {0, 1, 0, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        map = new int[M][N];
        dp = new int[M][N];

        for(int r = 0; r < M; r++) {
            st = new StringTokenizer(br.readLine());
            for(int c = 0; c < N; c++) {
                map[r][c] = Integer.parseInt(st.nextToken());
                dp[r][c] = -1;
            }
        }

        System.out.println(dfs(0, 0));
    }

    static int dfs(int r, int c) {
        if(r == M - 1 && c == N - 1) {
            return 1;
        }

        if(dp[r][c] != -1) {
            return dp[r][c];
        }

        dp[r][c] = 0;

        for(int i = 0; i < 4; i++) {
            int nextY = DIR_Y[i] + r;
            int nextX = DIR_X[i] + c;

            if(nextY < 0 || M <= nextY) continue;
            if(nextX < 0 || N <= nextX) continue;
            if(map[r][c] <= map[nextY][nextX]) continue;

            dp[r][c] += dfs(nextY, nextX);
        }

        return dp[r][c];
    }
}