BOJ_1520_내리막 길 (Java)

[Gold III] 내리막 길 - 1520

문제 링크

### 성능 요약

메모리: 48580 KB, 시간: 488 ms

### 분류

깊이 우선 탐색, 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색

### 제출 일자

2025년 4월 15일 22:39:47

### 문제 설명

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

### 입력

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

### 출력

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

문제 풀이

Top-Down DP + dfs를 활용하려 하다가 메모이제이션을 해도 시간복잡도가 dfs는 매우 커지니까 (500x500이면 최대 $3^{500}$) 순수 Bottom-up DP로 풀었다.

dp[r][c] 는 (r, c) 에서 맨 오른쪽 아래로 가는 경우의 수다. 그러므로 맨 오른쪽아래 위치 dp값은 1이다.

코드

package BOJ_1520_내리막길;

/**
 * 22:10 ~ 22:40
 * Author: nowalex322, Kim HyeonJae
 */

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

public class Main {
    class Node implements Comparable<Node>{
        int r, c, h;
        public Node(int r, int c, int h) {
            this.r = r;
            this.c = c;
            this.h = h;
        }

        public int compareTo(Node o) {
            return this.h - o.h;
        }
    }
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, M;
    static int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
//        br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_1520_내리막길/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        int[][] board = new int[N][M];
        int[][] dp = new int[N][M];
        dp[N-1][M-1] = 1;

        PriorityQueue<Node> nodes = new PriorityQueue<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                int num = Integer.parseInt(st.nextToken());
                board[i][j] = num;
                nodes.add(new Node(i, j, num));
            }
        }

        while(!nodes.isEmpty()) {
            Node curr = nodes.poll();

            for(int k=0; k<4; k++) {
                int nr = curr.r + dr[k];
                int nc = curr.c + dc[k];
                if(isValid(nr, nc)){
                    if(isLow(curr.h, board[nr][nc])){

                        dp[nr][nc] += dp[curr.r][curr.c];
                    }
                }
            }
        }

        for(int i=0; i<N; i++){
            System.out.println(Arrays.toString(dp[i]));
        }

        System.out.println(dp[0][0]);
        br.close();
    }

    private static boolean isValid(int r, int c) {
        return r >= 0 && r < N && c >= 0 && c < M;
    }

    private static boolean isLow(int curr, int next){
        return curr < next;
    }
}