[BOJ] 1520. 내리막 길

dfs와 dp를 같이 활용하는 문제였다.

맨처음 문제를 보았을때 백트래킹으로 접근해보았다. 하지만 M과 N이 최대 500을 가지고 있기에 시간초과를 우려하게 되었다. 따라서 메모제이션을 활용할 수 있는 dp를 같이 접목해보았다. dp[i][j]라는 배열을 두고 i,j에서의 M,N을 도달하는 방법의 수를 가지도록 설계를 하였다. 즉 dfs를 돈 경험이 있는 i,j 위치를 탐색해야할때 다시 dfs를 도는 것이 아니라 dp[i][j] 값만을 반환하도록 메모이제이션을 활용해주었다. 이 때 주의할점은 이차원 dp 배열의 초기값을 -1로 하는 것이랑 dfs 메소드가 dp[i][j]를 반환하도록 설계하는 것이다.

package algostudy2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_1520_내리막길 {
    static class Pos {
        int i, j;
 
        public Pos(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
 
    static int[] di = {-1, 0, 1, 0};
    static int[] dj = {0, 1, 0, -1};
 
    static int N, M;
    static int[][] map;
    static int[][] dp;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        map = new int[N][M];
        dp = new int[N][M];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1;
            }
        }
 
        System.out.println(dfs(0, 0));
    }
 
    static int dfs(int i, int j) {
        if (i == N - 1 && j == M - 1) {
            return 1;
        }
 
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
 
        dp[i][j] = 0;
        for (int dir = 0; dir < 4; dir++) {
            int nextI = i + di[dir];
            int nextJ = j + dj[dir];
 
            if (nextI < 0 || nextI >= N || nextJ < 0 || nextJ >= M) {
                continue;
            }
 
            if (map[i][j] > map[nextI][nextJ]) {
                dp[i][j] += dfs(nextI, nextJ);
            }
        }
 
        return dp[i][j];
    }
}