[백준] 내리막 길

참고: www.acmicpc.net/problem/1520

1520번: 내리막 길

 

- dp 문제

- 풀이 보고 함

- bfs 로 풀려고 했으나 시간 초과

- dfs + 메모이제이션 이용한 dp로 푸는 방법이 결론..

 

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

class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public boolean canMove(int x, int y, int N, int M) {
        return this.x >= 0 && this.x < N &&
               this.y >= 0 && this.y < M;
    }

}

public class Solution {
    // 방향 하 -> 우 -> 상 -> 좌
    private static int[] dx = new int[]{0, 1, 0, -1};
    private static int[] dy = new int[]{1, 0, -1, 0};
    private static int[][] block;
    private static int[][] dp;
    private static int N;
    private static int M;

    private static int dfs(int x, int y) {
        if(x == 0 && y == 0) return 1;

        if(dp[x][y] == -1) {
            dp[x][y] = 0;
            for (int i = 0; i < 4; i++) { // 4방향
                int nx = x + dx[i];
                int ny = y + dy[i];
                Point p = new Point(nx, ny);
                if(p.canMove(nx, ny, N, M)) {
                    if(block[x][y] < block[nx][ny]) {
                        dp[x][y] += dfs(nx, ny);
                    }
                }

            }
        }

        return dp[x][y];
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        block = new int[N][M];
        dp = new int[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                block[i][j] = sc.nextInt();
                dp[i][j] = -1;
            }
        }
        dfs(N-1, M-1);
        System.out.println(dp[N-1][M-1]);

    }
}