[백준] 1520. 내리막길 (DP/Java)

[백준] 1520. 내리막길

 

📌 풀이 과정

DFS로 4방향 + 내리막길로만 탐색하고, 백트래킹으로 풀었지만

네 어김없이 시간초과가 뜬다.

시간복잡도를 고려하는 방법에 대해서 공부할 필요가 있음을 느낀다..

DFS로 모든 가능한 경로를 탐색한다.
But, 이미 계산한 위치의 경로 수를 재사용하여 중복 계산을 방지해야 한다.

`dp[x][y]` = 현재 위치(x, y)에서 도착지점(M-1, N-1)까지의 경로의 수

`dfs(x, y)` = 현재 위치(x, y)에서 출발하여 도착점까지 가는 경로의 수를 반환한다.

 

1. (0, 0)에서 시작해 가능한 모든 내리막길로 이동한다.
2. 아직 계산되지 않은 위치인 경우 DFS를 통해 경로를 계산한다. `dp[x][y] == -1`
3. 이미 계산된 곳으로, 해당 위치에서 가는 경로 수를 재사용한다. `dp[x][y] != -1`

3	2	2	2	1
1	-1	-1	1	1
1	-1	-1	1	-1
1	1	1	1	-1

최종적으로, dp[0][0]에 (0, 0)에서 (M-1, N-1)까지의 경로 수가 저장된다.

DFS 완탐으로 작성한 코드

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

public class Main {

    static int N, M, ans;
    static int[][] map;
    static boolean[][] visited;
    static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 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];
        visited = new boolean[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());
            }
        }

        ans = 0;
        dfs(0, 0, map[0][0]);
        System.out.println(ans);
    }

    private static void dfs(int x, int y, int hill){
        if(x == M-1 && y == N-1){
            ans++;
            return;
        }
        for(int i = 0; i < 4; i++){
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];

            if(nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
            if(map[nx][ny] < hill && !visited[nx][ny]){
                visited[nx][ny] = true;
                dfs(nx, ny, map[nx][ny]);
                visited[nx][ny] = false;
            }
        }
    }

}

 

✨ 제출 코드

메모리: 35860 KB

시간: 348 ms

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

public class Main {

    static int N, M;
    static int[][] map;
    static int[][] dp;
    static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 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());
            }
        }

        for(int i = 0; i < M; i++){
            Arrays.fill(dp[i], -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[x][y] = 0;

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

                if(nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
                if(map[x][y] > map[nx][ny]) { // 내리막길인 경우
                    dp[x][y] += dfs(nx, ny);
                }
            }
        }

        // 이미 해당 위치의 경우의 수가 계산된 경우
        return dp[x][y];
    }

}