[백준 1520번] 내리막 길

문제 링크: 1520번 제목

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

 

언젠가 굉장히 무난하게 풀었던 문제인데, 이번엔 굉장히 어렵게 풀었다. 일단 다음에 다시 풀 때에는, 다른 방식으로도 풀어볼 예정이다(https://hoondev.tistory.com/81).

 

결론을 요약하면 다음과 같다.

P(i, j)를 (i, j)로부터 목적지까지 가는 경로의 개수라고 하면,
P(i, j) = sum( { P(a, b) | (a,b)는 (i, j)와 인접 & (a, b)는 (i, j)보다 고도가 낮음 } )

 

아래 코드에서 dp[i][j]에는 (i,j)에서 목적지까지 가는 경로의 개수를 저장하며, func(i, j)는 dp(i, j)를 채우는 함수이다.

 

간단하게만 따라가보자. 일단 여기서는 (0, 0)에서 출발해서 뻗어나가기로 한다. 어떻게 될지는 몰라도, (0, 0)에서 출발해서 목적지까지 가는 경로의 개수는, (0, 1)에서 출발해서 목적지까지 가는 경로의 개수와 (1, 0)에서 출발해서 목적지까지 가는 경로의 개수를 더한 것과 같다. 그렇다고 해서 dp[0][1]과 dp[1][0]을 바로 쓸 수는 없으니, f(0, 1)과 f(1, 0)을 더하여 이를 dp[0][0]에 저장해줌으로서 f(0, 0)은 종료된다.

그렇다면, func(A)를 호출했을 때, func(B), func(C), ...를 거쳐서 func(A)가 다시 호출되는 일은 없을까? 결론부터 말하자면, "없다". func(A)가 func(B)를 호출했다는 것은, B 위치에 적힌 숫자가 A 위치에 적힌 숫자보다 작다는 것을 전제로 한다. 따라서 A > B > C > ...이므로 결코 func(A)는 다시 호출될 수 없다.

 

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

public class Main {
    static int[] dr = {0, 0, 1, -1};
    static int[] dc = {1, -1, 0, 0};
    static int rows, cols;
    static int[][] board = new int[500][500];
    static int[][] dp = new int[500][500];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        rows = Integer.parseInt(st.nextToken());
        cols = Integer.parseInt(st.nextToken());
        for (int i = 0; i < rows; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < cols; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                dp[i][j] = -1;
            }
        }

        // dp[i][j] = num of path from (i, j) to (rows-1, cols-1)
        System.out.println(func(0, 0));
    }

    static int func(int r, int c) {
        if (r == rows - 1 && c == cols - 1) {
            return 1;
        }
        if (dp[r][c] != -1) {
            return dp[r][c];
        }

        int sum = 0;
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
            if (board[nr][nc] >= board[r][c]) continue;
            sum += func(nr, nc);
        }

        return dp[r][c] = sum;
    }
}