boj 1520 내리막 길

www.acmicpc.net/problem/1520

1520번: 내리막 길

emoney96.tistory.com/189

boj 1937 욕심쟁이 판다

이 문제와 비슷한 풀이입니다.

dfs + dp를 사용하며

위의 문제는 칸의 수를 세어주었지만 이 문제는 (0, 0)에서 (N - 1, M - 1)까지 도달할 수 있는 경우의 수를 세어주는 문제입니다.

 

현재 칸보다 높이가 더 낮은 지점으로만 이동합니다.

(N - 1, M - 1)에 도달하면 1을 리턴하고 이미 방문한 좌표에는 해당 좌표의 dp[x][y]를 리턴해줍니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][] = new int[500][500];
    static int dp[][] = new int[500][500];
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int N, M;
 
    static int func(int x, int y) {
        if (x == N - 1 && y == M - 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 + direct[i][0];
            int ny = y + direct[i][1];
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                continue;
            if (list[x][y] <= list[nx][ny])
                continue;
 
            dp[x][y] += func(nx, ny);
        }
        
        return dp[x][y];
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], -1);
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                list[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        System.out.println(func(0, 0));
    }
}