내리막 길 / DFS 깊이우선탐색

https://www.acmicpc.net/problem/1520

2차원 Array가 주어졌을때 0,0에서 시작하여 상하좌우로 이동할 때, 항상 높은 값에서 낮은 값의 방향으로 이동 할 수 있는 모든 케이스에 대해 출력하라는 문제이다.

시간복잡도를 고려해야하는 문제로 dp를 이용해야한다.

dp를 이용하는 것은, 여러개의 경로를 계산하는 과정에서 중복된 경로를 고려해야 하기 때문이다.

 

 

/** 3번 내리막 길 */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    public static int N, M;

    static int graph[][];
    static int dp[][];

    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

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

        for(int i=0; i<N;i++) {
            for(int j=0; j<M; j++){
                graph[i][j] = sc.nextInt();
//                dp[i][j] = Integer.MIN_VALUE;
            }
        }
        sc.close();
/*
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String nm = br.readLine();
        N = Integer.parseInt(nm.split(" ")[0]);
        M = Integer.parseInt(nm.split(" ")[1]);

        graph = new int[N][M];
        dp = new int[N][M];

        for (int i = 0; i < N; i++) {
            nm = br.readLine();
            for (int j = 0; j < M; j++) {
                graph[i][j] = Integer.parseInt(nm.split(" ")[j]);
                // dp[i][j] = -1;
            }
        }

 */
        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i],Integer.MIN_VALUE);
        }
        System.out.println(dfs(0, 0));

    }

    public static int dfs(int x, int y) {
        if(x == N-1 && y == M-1) {
            return 1;
        }
        if  (dp[x][y] != Integer.MIN_VALUE) {
            return dp[x][y];
        }
        else {
            dp[x][y] = 0;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx < N && nx >= 0 && ny < M && ny >= 0) {
                    if (graph[x][y] > graph[nx][ny]) {
                        dp[x][y] += dfs(nx, ny);
                    }
                }
            }
        }
        return dp[x][y];


    }
}