[백준] 1520. 내리막 길

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

 

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

출력

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

---

예제 입력 1

4 5
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10

예제 출력 1

3

---

N, M이 500이하이며 최대 크기가 25,000개이다. 각 시작점에서 도착점까지 하나씩 확인하면 무조건 시간 초과가 나니  DFS + DP로 접근해야 한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static int R, C;
    public static int[][] arr;
    public static int[][] dp;
    public static void main(String[] args) throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        arr = new int[R][C];
        dp = new int[R][C];

        for(int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < C; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1;  // 0도 경우의 수기 때문에 -1로 초기화
            }
        }
        int res = dfs(0, 0);
        bw.write(Integer.toString(res));
        br.close();
        bw.flush();
        bw.close();
    }
    public static int[] dr = {-1, 1, 0, 0};
    public static int[] dc = {0, 0, -1, 1};

    public static int dfs(int r, int c) {
        if(r == R - 1 && c == C - 1) {
            return 1;
        }
        if(dp[r][c] == -1) {
            dp[r][c] = 0;
            for(int d = 0; d < 4; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];

                if(nr >= 0 && nr < R && nc >= 0 && nc < C && arr[r][c] > arr[nr][nc]) {
                    dp[r][c] += dfs(nr, nc);
                }
            }
        } 
        return dp[r][c];
    }
}

주의할 점은 DP배열 초기화 시 경우의 수를 세기 위해 전부 -1로 초기화를 한다.

 

DFS의 종료 조건은 맨 오른쪽 아래에 도달 하였을 땐 위 또는 왼쪽에서 올 수 있는 경우의 수는 하나이니 1을 리턴해 주면 된다.

 

시작점(0, 0)에서 DFS를 할 때 dp배열을 기준으로 DP를 하고  다음 값(arr[nr][nc])이 현재값(arr[r][c])보다 더 작아야 내려 갈 수 있을 때 현재의 dp[r][c]에서 다음 dfs를 실행한 값을 더해준다.