[PS] BOJ1520 내리막 길 ( DP + DFS ) with JAVA

 

1520번: 내리막 길

 

 

◎ 문제풀이

 

처음에는 대부분 DFS로 풀었다가 시간초과를 마주한다. 

 

 

 

 

한 경로가 위처럼 이동했다고 해보자. 경로가 지나간 노드는 모두 방문된 노드가 된다. 보통의 DFS 풀이처럼 한번 방문한 노드를 다시 방문하지 못하도록 조건을 건다면 DFS의 시간복잡도는 O(N+E)가 된다. ( N은 노드의 개수, E은 간선의 개수 )

 

N은 최대 2,500개이고 간선은 노드 하나당 4개를 갖는다고 가정하면 10,000개이다. 시간복잡도가 O(N+E)면 충분히 시간제한 2초안에 풀 수 있다. 그러나 위 문제는 한번 방문한 노드도 다시 방문할 수 있다. 

 

 

 

 

끝노드까지 도달하는 모든 경우의 수를 구하는 문제이므로, 한번 방문한 노드도 다른 경로에 의해 다시 방문될 수 있다.  그러면 시간복잡도는 기하급수로 증가한다. 최대 노드의 개수가 2500이다. 그럼 DFS의 재귀호출 최대 깊이도 2500이 된다. 한번 재귀호출될 때마다, 상하좌우 4번 DFS 호출을 하므로, 4의 2500승이 DFS의 시간복잡도가 된다. 시간제한 2초를 넘어선다. 

 

이 문제를 시간 안에 풀려면 DFS를 DP와 연계해서 풀어야 한다. DP는 메모리제이션을 활용하여 완전탐색의 시간복잡도를 줄이는 방법이다. 메모리제이션을 하려면 DP테이블을 만들어야 한다.

 

DP테이블에는 각 노드에서 끝노드까지 가는 경로의 수가 저장된다.

DFS로 방문한 노드를 시작노드로 하여 상하좌우를 DP의 경우로 한다.

상하좌우를 DFS 탐색하여 끝노드까지 도달하면 1을 반환한다. 

만약 DP테이블이 이미 초기화되어 있다면 재귀호출을 멈추고 메모리제이션으로 시간복잡도를 줄인다. 

 

 

◎ 코드

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

//BOJ1520 내리막 길 ( DP + DFS )
public class Main {
    static int m,n,ans;
    static int[][] graph,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());
        graph = 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++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1;
            }
        }

        dfs(0,0);
        System.out.println(dp[0][0]);

    }

    public static int dfs(int x, int y){

        if(x==n-1&&y==m-1) return 1;
        if(dp[y][x]!=-1) return dp[y][x];

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

            if(isValidate(nx,ny)){
                if(graph[y][x] > graph[ny][nx] ) {
                    dp[y][x] += dfs(nx,ny);
                }
            }
        }

        return dp[y][x];

    }
    public static boolean isValidate(int x, int y){
        if(x>=0&&y>=0&&x<n&&y<m) return true;
        else return false;
    }

}