백준 - 내리막길

 

 

 

DFS + DP

 

기본적으로 맵의 가로, 세로 최대는 500이다.

만약, (0, 0)에서 (499, 499)까지 간다고 가정하자

해당 경우의 수는 굉장히 커진다.

 

 

예를 들어, (0, 0)에서 (200, 200)으로 가는 경로가 10000이고 (200, 200)에서 (499, 499)까지 간다고 가정했을 때, 경로가 10000이라면 약, 10억가지의 경우의 수가 나온다.

 

 

밑의 두가지 코드의 차이점은 아래와 같다.

1번 코드 : (200, 200) 방문시 DP를 통해 (499, 499)까지 도달 가능하다고 판단하고 돌아간다.

2번 코드 : 항상 끝까지 방문한다.

 

위의 차이점으로 DP를 통해 시간복잡도를 낮출 수 있다.

 

 

추가사항

- 노드1에서 노드2까지 가는 경우의 수를 구하라

- 백준 점프 문제와 유사하다.

 

 

 

정답 코드

package BAEKJOON_DP;


import java.util.*;

// 내리막 길
public class Q7 {
    public static int[][] map;
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, -1, 0, 1};
    public static long[][] dp = new long[501][501];
    public static int n;
    public static int m;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        // 맵 생성
        map = new int[n][m];
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                map[i][j] = sc.nextInt();
                dp[i][j] = -1;
            }
        }
        dfs(0, 0);
        System.out.println(dp[0][0]);
    }
    public static long dfs(int x, int y){
        // 목적지 도달
        if(x == n-1 && y == m-1){
            return 1;
        }
        // 이미 방문 한 노드
        if(dp[x][y] != -1){
            // (x, y)에서 (n-1, m-1)까지 갈 수 있는 경우의 수 반환
            return dp[x][y];
        }
        // 방문처리 및 값 초기화
        dp[x][y] = 0;
        // 인접 노드 탐색
        for(int i=0; i<4; i++){
            int next_x = x + dx[i];
            int next_y = y + dy[i];
            // 범위 벗어남
            if(next_x < 0 | next_x >= n | next_y < 0 | next_y >= m){
                continue;
            }
            // 다음 노드가 현재 노드가 작을때만 이동
            if(map[next_x][next_y] < map[x][y]){
                // 해당 노드에서 목적지까지 가는 모든 경우의 수 더한다.
                dp[x][y] += dfs(next_x, next_y);
            }
        }
        return dp[x][y];
    }
}

 

 

 

 

시간 초과 코드

- 추가적으로, 아래의 코드에서 visited를 dfs와 같이 넘겨준다면, 메모리 초과가 발생한다.

package BAEKJOON_DP;


import java.util.*;

// 내리막 길
public class Q7 {
    public static int[][] map;
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, -1, 0, 1};
    public static int n;
    public static int m;
    public static boolean[][] visited;
    public static long answer = 0;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        // 맵 생성
        map = new int[n][m];
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                map[i][j] = sc.nextInt();
            }
        }
        // (0, 0) 시작
        visited = new boolean[n][m];
        dfs(0, 0);
        System.out.println(answer);
    }
    public static void dfs(int x, int y){
        // 목적지 도달
        if(x == n-1 && y == m-1){
            answer += 1;
            return;
        }
        // 이미 방문했던 노드
        if(visited[x][y]){
            return;
        }
        for(int i=0; i<4; i++) {
            int next_x = x + dx[i];
            int next_y = y + dy[i];
            if (next_x < 0 | next_x >= n | next_y < 0 | next_y >= m) {
                continue;
            }
            if (map[x][y] > map[next_x][next_y]) {
                visited[x][y] = true;
                dfs(next_x, next_y);
                visited[x][y] = false;
            }
        }
    }
}