DP ( DFS 이용해서 )

백준 1520번을 Java를 이용해 풀어보았다. 결국 또 못 풀었다. 나는 DP 고자다. 씹

문제 링크 첨부한다.
https://www.acmicpc.net/problem/1520

그냥 DFS, 시간 초과

문제에서 애초에 정답인 H값이 10억 이하라고 했으니 그냥 DFS 때려서 모든 경로에 대해 확인하게 되면 시간 초과가 날 게 뻔했다. 하지만 어차피 DP를 이용해 푸는 풀이는 생각해내지 못해서 그냥 DFS 때렸더니 역시나 20%에서 시간 초과가 떴다.

DP를 이용한 DFS

각 지점에 대하여 도착 지점까지 내리막길만 이용해서 갈 수 있는 경로의 수들을 구해주는데, dp 배열을 따로 선언해서 아직 방문되지 않은 지점은 -1, 방문한 지점은 도착점까지 몇 개의 가능한 경로가 있는지 갱신해주는 방식으로 DFS와 DP를 섞어서 풀면 된다.

즉, dfs(0,0)의 값이 곧 우리가 원하는 답의 값이다.
만약 dfs(도착 지점 r, 도착지점 c)를 넣게 되면 1이 나오게 되는 것이다.

코드는 아래와 같다.

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

public class boj1520 {
    static int[][] map, dp;
    static int row,col;
    static int[][] move = { {0,-1}, {0,1}, {-1,0}, {1,0} };

    static int dfs(int r, int c){
        if(r==row-1 && c == col-1)
            return 1;
        else if(dp[r][c]!= -1)
            return dp[r][c];

        dp[r][c] = 0;
        for(int dir=0; dir<4; dir++){
            int nxt_r = r + move[dir][0];
            int nxt_c = c + move[dir][1];
            if(nxt_r<0 || nxt_r>=row || nxt_c<0 || nxt_c>=col)  continue; // 범위 밖이면 패스
            if(map[r][c] - map[nxt_r][nxt_c] <= 0)  continue; // 낮아지지 않으면 패스

            dp[r][c] += dfs(nxt_r, nxt_c);
        }

        return dp[r][c];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(bfr.readLine());
        row = Integer.parseInt(stk.nextToken());
        col = Integer.parseInt(stk.nextToken());
        map = new int[row][col];
        dp = new int[row][col];

        for(int i=0; i<row; i++){
            stk = new StringTokenizer(bfr.readLine());
            for(int j=0; j<col; j++){
                map[i][j] = Integer.parseInt(stk.nextToken());
                dp[i][j] = -1;
            }
        }

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

DP 문제를 계속해서 풀어보고 있는데 풀 때마다 너무 새롭다. 다 독립 시행같이 느껴져서 개빡친다. 내가 그냥 멍청한 것도 있지만... 늘지를 않냐 씨바..