[백준] 내리막길 Java

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

1520번: 내리막 길

 

 

조건

 

1. 지도의 숫자는 해당 칸의 높이

2. 시작 지점은 (0,0) 도착 지점은 (m, n)

3. 항상 내리막길만 이용 (이전 칸의 높이보다 낮은 칸으로만)

4. 상하좌우로만 이동

 

 

이 조건을 만족하는 경로의 개수를 모두 구하는 문제

"경로의 개수" 를 구해야 하기 때문에 dfs 를 사용

 

재귀를 통한 깊이 우선 탐색으로 조건에 나온 현재 지점보다 낮은 경로 탐색

 

 

 

 

public class Main {
    
    static int m, n;
    static int dm[] = {1, 0, -1, 0};
    static int dn[] = {0, 1, 0, -1};
    static int dp[][];
    static int input[][];
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(reader.readLine());

        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        input = new int[501][501];
        dp = new int[501][501];
        for(int i=0; i<m; i++){
            st = new StringTokenizer(reader.readLine());
            int idx = 0;
            while(st.hasMoreTokens()){
                input[i][idx] = Integer.parseInt(st.nextToken());
                dp[i][idx++] = -1;
            }
        }

        int result = dfs(0,0);

        System.out.println(result);
    }
    
    
    public 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 nextX = x+dm[i];
            int nextY = y+dn[i];

            if(nextX >= 0 && nextY >= 0 && nextX <m && nextY < n && input[nextX][nextY] < input[x][y]){
                dp[x][y] += dfs(nextX, nextY);
            }
        }


        return dp[x][y];
    }
}