BOJ 1520 내리막 길

https://www.acmicpc.net/problem/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

---

코드

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 M, N;
    static int[] dirR = {0, -1, 0, 1}, dirC = {1, 0, -1, 0};
    static int[][] map, 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];
        dp = new int[M][N];
        // 방문하지 않은 곳을 표현하기 위해 dp를 -1로 초기화
        for (int i = 0; i < M; i++) Arrays.fill(dp[i], -1);

        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());
        }

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

    static int dfs(int r, int c) {
        // 골인 지점에 도달했을 경우 1 반환
        if(r == M - 1 && c == N - 1) return 1;

        // 만약 방문하려는 위치가 이전에 방문하여 검사한 적이 있는 경우, 해당 위치의 dp를 반환
        if(dp[r][c] != -1) return dp[r][c];

        // 방문한 지점은 0으로 초기화 후 이후에 방문 경로 수를 더함
        dp[r][c] = 0;
        for (int i = 0; i < dirR.length; i++) {
            int newR = r + dirR[i], newC = c + dirC[i];
            boolean isInside = newR >= 0 && newR < M && newC >= 0 && newC < N;
            if(isInside && map[newR][newC] < map[r][c]) dp[r][c] += dfs(newR, newC);
        }

        // 최종적으로 해당 위치에서 계산된 방문 경로 수를 반환
        return dp[r][c];
    }
}