[Baekjoon] #1520 내리막 길

시작점에서 끝점까지 도달하는 경로의 개수를 세는 문제로 깊이 우선 탐색 알고리즘으로 풀이(DFS)

하지만, DFS로만 풀게 되면 시간 초과가 발생한다.

이를 위해 이미 탐색해서 경로의 개수가 파악된 경로를 재 탐색하는 것을 방지하기 위해 다이나믹 프로그래밍 알고리즘을 이용한다.

• dp[x][y]는 최종 경로까지 이동 경로의 개수를 더하며, 이미 최종 경로까지의 이동 경로가 정해진 경우 dp 값을 활용하여 탐색 없이 이동 경로의 개수만 구할 수 있도록 처리한다.

// input
2 2 
20 10
12 7

// 배열[x][y] 부터 배열[m-1][n-1] 까지의 이동 경로 개수(dp[x][y])는 아래와 같다
2 1
1 1

import java.util.Scanner;

public class Main {

    static int n;
    static int m;
    static int[][] map;
    static int[][] visit;
    static int[][] dp;

    static int[] xx = {-1, 0, 1, 0};
    static int[] yy = {0, 1, 0, -1};

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Scanner sc = new Scanner(System.in);

        m = sc.nextInt();
        n = sc.nextInt();

        map = new int[m][n];
        visit = new int[m][n];
        dp = new int[m][n];

        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                map[i][j] = sc.nextInt();
            }
        }

        dp[m-1][n-1] = 1;
        getDFS(0,0);

        System.out.println(dp[0][0]);

    }

    public static void getDFS(int x, int y) {
        if(x == m-1 && y == n-1) return;

        if(visit[x][y] == 1) return;

        visit[x][y] = 1;

        for(int i=0;i<4;i++) {
            int ax = x+xx[i];
            int ay = y+yy[i];

            if(ax >= 0 && ax < m && ay >= 0 && ay<n && map[x][y] > map[ax][ay]) {
                if(dp[ax][ay] != 0) {
                    dp[x][y] += dp[ax][ay];
                    continue;
                } else {
                    getDFS(ax,ay);
                    dp[x][y] += dp[ax][ay];
                }
            }
        }
    }

}