[JAVA/백준/1520] 내리막길 / DP, DFS

1520번: 내리막 길

 

이 문제는 출발점에서 도착점까지 가는 경로의 수를 구하는 것이다

DFS를 통해 도착하는 모든 경로를 얻을 수 있지만 시간초과가 발생하게 된다

같은 경로를 중복해서 탐색할 수가 있기 때문에 시간 복잡도를 효율적으로 개성해야 한다

 

따라서 DFS + DP를 이용해 풀이를 했다

 

우선, DFS를 이용해 출발점에서 도착점까지 모든 경로를 탐색하는데 현재 위치에서 갈 수 있는 높이가 낮은 지점으로 이동하면서 경로의 수를 누적한다. 이미 계산한 경로는 중복 계산하지 않도록 메모이제이션을 이용해 저장된 값을 이용한다. 이를 위해서

1. DP 배열을 -1로 초기화 한다. (이미 지나가지 않은 경로를 의미)
2. 탐색을 하면 해당 DP 값을 0으로 초기화 한다.
3. DFS를 진행하며 도착지점을 찾는다. (탐색하는 경로 중 DP값이 -1이 아니라면 이미 탐색이 끝난 경로로 보고 탐색을 종료한다)

자세한 건 주석으로 표시했다

 

 

결과 코드

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

public class Main {

    private static int M, N;  // 입력받은 지도의 행, 열
    private static int[][] map;  // 지도 정보를 저장하는 배열
    private static int[][] dp;  // 메모이제이션을 위한 배열

    private static int[] moveX = {-1, 1, 0, 0};  // x 좌표의 변화량
    private static int[] moveY = {0, 0, -1, 1};  // y 좌표의 변화량


    public static void main(String[] args) throws IOException {
        Main.start();
    }


    private static void start() 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;
            }
        }

        // 계산
        dfs(0, 0);  // 출발점인 (0,0)부터 DFS 탐색 시작

        // 출력
        System.out.println(dp[0][0]);  // 출발점에서부터 도착점까지 이동할 수 있는 경로 수 출력
    }

    private static int dfs(int x, int y) {
        // 도착점에 도달하면 경우의 수 1을 리턴
        if (x == M - 1 && y == N - 1) {
            return 1;
        }

        // 메모이제이션을 이용하여 이미 계산한 값이면 해당 값을 리턴
        if (dp[x][y] != -1) {
            return dp[x][y];
        } else {
            dp[x][y] = 0;  // 계산한 적이 없으면 0으로 초기화
        }

        // 현재 위치에서 4방향으로 이동하면서 경로 수를 구함
        for (int i = 0; i < 4; i++) {
            int newX = x + moveX[i];  // 새로운 x 좌표
            int newY = y + moveY[i];  // 새로운 y 좌표

            // 지도 범위를 벗어나면 continue
            if (newX < 0 || newY < 0 || newX >= M || newY >= N) {
                continue;
            }

            // 내리막길이 아니면 continue
            if (map[newX][newY] >= map[x][y]) {
                continue;
            }

            // 경로 계산
            dp[x][y] += dfs(newX, newY);
        }

        return dp[x][y];
    }
}