백준 1520번 - 내리막 길

문제

백준 1520번 - 내리막 길

아이디어

• DFS + DP
• 단순하게 DFS나 BFS로 풀면 시간초과가 발생한다.
• 단순 DFS라면 끝점만 찍고 오면 끝이겠지만 이 문제의 경우 가능한 모든 경로의 개수를 구하는 것이므로 메모이제이션을 사용해야 한다.
• dp 배열을 현재 자리에서 도착 지점까지 갈 수 있는 경로의 개수라고 가정한다.
• 메모이제이션을 사용하면 처음 도착 지점까지 갈 수 있는 경로를 확인하고 또 다른 경로를 확인할 때 다시 처음부터 확인하지 않고 가능했던 경로에 이어서 또 다른 경로를 확인할 수 있다.

예상 시간 복잡도

• 메모이제이션을 사용하여 모든 지점에 대해 한번씩만 확인 가능하다.
• 예상 시간 복잡도 : O(M x N)

코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ_1520 {

    static int[][] map;
    static int m, n;
    static int[][] dp;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 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 i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1;
            }
        }

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

    private static int dfs(int x, int y) {
        if (x == m - 1 && y == n - 1) { //도착 지점 가능, 경우의 수 추가
            return 1;
        }

        if (dp[x][y] != -1) { //dp 배열을 방문 체크의 용도로도 가능하다.
            return dp[x][y];
        }

        dp[x][y] = 0; //가능한 경로 방문 확인

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < m && ny >= 0 && ny < n) { //범위 체크
                if (map[nx][ny] < map[x][y]) { //조건 체크
                    dp[x][y] += dfs(nx, ny); //현재 위치에서 가능한 경로의 개수 합
                }
            }
        }

        return dp[x][y];
    }
}