[백준] 1520번 - 내리막 길 [Java]

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

 

[백준] 1520번 - 내리막 길 [Java]

[백준] 1520번 - 내리막 길 [Java]

---

1.  아이디어

 

Top-Down 다이나믹 프로그래밍을 활용하면 경로의 개수를 구할 수 있다.

---

2. 문제풀이

 

특정 위치에서 도착 지점까지 갈 수 있는 경로의 개수는 특정 위치 상하좌우에 위치한 내리막길에서 도착지점까지 갈 수 있는 경로의 개수의 합이다. 이를 dfs로 도착 지점이면 1을 반환하고 도착 지점이 아니면 상하좌우에 내리막길에서 경로의 개수를 더해서 반환하도록 짜면 로직은 구현이 된다.

 

시간 초과 문제를 해결하기 위해 메모이제이션을 해야하는데 지도와 같은 크기의 2차원 dp 배열을 선언하고 dp 배열에는 특정 위치에서 도착 지점에 갈 수 있는 경로의 개수를 저장한다. 이후 dfs에서 dp 배열에 경로가 저장되어 있으면 해당 개수를 반환하고 저장되어 있지 않으면 이전처럼 재귀로 탐색하도록 구현했다. 여기서 dp 배열을 0으로 초기화해서 사용하면 도착하지 못하는 경로에 대한 메모이제이션이 안돼서 dp 배열을 -1로 초기화하고 도착하지 못하는 경로는 0으로 메모이제이션이 되게 구성해야 한다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {

    private static final int[] dr = {-1, 0, 1, 0};
    private static final int[] dc = {0, 1, 0, -1};
    private static int M;
    private static int N;
    private static int[][] map;
    private static int[][] dp;

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

        System.out.println(dfs(0, 0));
    }

    private static int dfs(int r, int c) {
        if (r == M - 1 && c == N - 1) return 1;
        if (dp[r][c] != -1) return dp[r][c];

        int sum = 0;
        for (int dir = 0; dir < 4; dir++) {
            int nr = r + dr[dir];
            int nc = c + dc[dir];

            if (nr < 0 || nr >= M || nc < 0 || nc >= N) continue;
            if (map[nr][nc] >= map[r][c]) continue;

            sum += dfs(nr, nc);
        }

        return dp[r][c] = sum;
    }
    
}

---

4. 후기