[BOJ]1520 - 내리막 길(G3)

문제 링크

1520-내리막 길

입력

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

M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

출력

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

문제 풀이

dp를 사용해 메모이제이션과 현재까지 올 수 있는 경로의 수 저장

dp값이 초기값이면 방문하지 않았다는 의미이므로 maps에서 주변에 더 작은 값이 존재하는지 확인하여 이동
초기값이 아니면 현재 dp에 저장된 값을 반환

처음에 dp값 초기화 안해서 좀 헤맸다
초기화를 하지 않으면 기본적으로 0으로 저장되는데, 그렇게되면 이동할 수 있는 경로가 0이라는 의미
즉, 이동할 수 있는 경로가 없는데 계속해서 불필요한 연산 진행
-> dp값 -1로 초기화

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

public class Main {

    static int N, M;
    static int[][] maps, dp;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};

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

        maps = 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++) {
                maps[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1;
            }
        }

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

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

        if (dp[x][y] != -1) {
            return dp[x][y]; // 이미 지나간 경우
        }

        dp[x][y] = 0;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= M || nx < 0 || ny >= N || ny < 0) continue;

            // x,y의 높이가 nx,ny의 높이보다 높아야 이동 가능
            if (maps[x][y] > maps[nx][ny]) {
                dp[x][y] += dfs(nx, ny);
            }
        }
        return dp[x][y];
    }
}