[백준]1520번 내리막 길(java)

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

1520번: 내리막 길

 

핵심

이 문제는 DFS로 풀면 시간초과가 나게 된다. 따라서 DP를 함께 사용한다.

이미 탐색한 부분은 다시 탐색하지 않는 방법을 이용한다.

 

정답 코드

import java.util.Scanner;

public class Main {
    static int M;
    static int N;
    static int[][] map;
    static int[] dy = {1, 0, -1, 0};
    static int[] dx = {0, 1, 0, -1};
    static int[][] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        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(0, 0));
    }

    static int dfs(int y, int x) {
        if (y == M - 1 && x == N - 1) {
            return 1;
        }
        if (dp[y][x] != -1) {
            return dp[y][x];
        }

        dp[y][x] = 0;

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

            if (0 > moveX || 0 > moveY || moveX >= N || moveY >= M) {
                continue;
            }
            if (map[y][x] > map [moveY][moveX]){
                dp[y][x] += dfs(moveY,moveX);
            }
        }
        return dp[y][x];
    }
}

해설

DP를 -1로 초기화시킨다. -1은 방문하지 않은 것을 의미한다. 0 이상의 수 도착 가능한 경로의 수

시작점에서 끝지점까지 DFS를 사용하지만, 이미 탐색한 경로의 개수가 입력된 지점을 다시 탐색하려 하면,

저장된 경로의 개수를 반환한다.

아래 사진을 보면 이해가 쉽게 될 것이다.

 

반대로 아직 입력이 안된 지점은 0을 설정하고, 해당 지점에서 부터 dfs 해서 도착한 횟수의 합을 저장시킨다.

이제 [0,0] 에는 DP로부터 더해진 경로의 합이 담겨있게 된다.

 

 

배운 점 

맨 처음 DFS로만 풀려고 하였었는데, 풀면서도 시간초과가 날 것 같다는 생각을 하였다.

예상대로 단순하게 풀리지 않았다. DP를 사용해야 할 것 같다고 생각은 했지만, 

어떤 식으로 사용할지는 쉽게 떠오르지 않았다.

이는 아마 DP에 대한 지식이 부족하다는 의미인 것 같다.

요즘 알고리즘을 프로그래머스 위주로 단계별로 풀고 있는데, 특정 알고리즘을 익숙하게 공부하는 식으로 

학습 방법을 바꿔야겠다.