백준 1520 내리막 길(JAVA)

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

1520번: 내리막 길

문제 유형: DFS, DP

 

 

문제 풀이

이 문제는 dfs로 돌리면서, 오른쪽 끝점까지 갔던 경로를 dp로 저장하면서 푸는 문제이다.

예를 들어 (3,3)에서 (10,10)으로 가는 경로가 3이라 했었을 때 (1,1)에서 출발하여 (3,3)에 도착하면,

(10,10)까지 가지 않아도 경로를 알 수 있게 되는 것이다. 

 

전체 코드

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


public class Main {
    static class XY{
        int x;
        int y;

        public XY(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    static int next_x[] = {1,-1,0,0};
    static int next_y[] = {0,0,1,-1};
    static int map[][];
    static int n;
    static int m;
    static int dp[][];

    static int DFS(XY start){
        if(start.x == n - 1 && start.y == m - 1) return 1;

        if(dp[start.x][start.y] != -1) return dp[start.x][start.y];

        dp[start.x][start.y] = 0;
        for(int i = 0;i<4;i++){
            int nextx = start.x + next_x[i];
            int nexty = start.y + next_y[i];
            if(nextx < 0 || nexty < 0 || nextx >=n || nexty >= m) continue;

            if(map[nextx][nexty] < map[start.x][start.y]) dp[start.x][start.y] += DFS(new XY(nextx,nexty));
        }
        return dp[start.x][start.y];

    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        dp = new int[n][m];
        for(int arr[] : dp){
            Arrays.fill(arr, - 1);
        }
        for (int i = 0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0;j<m;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        System.out.println(DFS(new XY(0,0)));

    }
}