백준 1520번 내리막 길 :: 마이구미

이 글은 백준 알고리즘 문제 1520번 "내리막 길" 을 풀이한다.

풀이 방법은 DFS + DP(동적계획법) 을 통해 해결한다.

DFS - http://mygumi.tistory.com/102

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

단순히 모든 경로를 탐색한다면, 시간 초과를 경험하게 된다.

시간을 줄일 수 있는 방법은 다음과 같다.

20 지점에 오면 더이상 탐색할 필요가 없이 경로가 존재한다는 것을 찾을 수 있다.

존재하는 경로를 활용하는 방법으로써, 동적계획법을 이용할 수 있다.

dp[y][x] = (y, x) 지점일 때 존재하는 경로의 갯수

DFS를 완벽히 이해하고 있다면, 쉽게 코드를 이해할 수 있다.

* dp배열을 -1로 초기화한 이유는 방문여부를 위함이다.

static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, -1, 0, 1 };
static int[][] map, dp;
static int m, n;
 
private void solve() {
    m = sc.nextInt();
    n = sc.nextInt();
    map = new int[m][n];
    dp = new int[m][n];
 
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            map[i][j] = sc.nextInt();
            dp[i][j] = -1;
        }
    }
    System.out.println(dfs(m - 1, n - 1));
}
 
public static int dfs(int y, int x) {
    if (y == 0 && x == 0) {
        return 1;
    }
 
    if (dp[y][x] == -1) {
        dp[y][x] = 0;
        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + x;
            int ny = dy[i] + y;
 
            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (map[y][x] < map[ny][nx]) {
                    dp[y][x] += dfs(ny, nx);
                }
            }
        }
    }
    return dp[y][x];
}