백준 1520 내리막길 Java: DFS와 메모이제이션으로 경로 수 세기

백준 1520번 ‘내리막길’은 왼쪽 위에서 오른쪽 아래까지 이동하는 경로의 수를 구한다. 이동할 때마다 반드시 더 낮은 칸으로 가야 하므로 같은 칸으로 되돌아오는 cycle은 생기지 않는다. 이 성질을 이용해 각 칸에서 목적지까지 갈 수 있는 경로 수를 DFS로 구하고 한 번 계산한 값은 memoization하면 된다.

• 백준 1520번 내리막길

단순 BFS로 세기 어려운 이유

일반 BFS는 최소 이동 횟수처럼 같은 거리 단위로 상태를 처리하는 데 잘 맞는다. 이 문제는 어떤 칸에 여러 경로가 합류한 뒤 다시 갈라질 수 있다. 한 칸을 처음 방문했다고 닫아 버리면 나중에 도착한 다른 경로의 수를 반영하지 못하고, 방문 처리를 없애면 같은 하위 문제를 반복해서 계산한다.

높이가 큰 칸에서 작은 칸으로만 간다는 조건은 모든 이동 방향에 순서를 만든다. 따라서 다음 두 접근이 가능하다.

• top-down: DFS로 낮은 칸을 탐색하고 칸별 경로 수를 memoization
• bottom-up: 높이가 높은 칸부터 처리하도록 정렬하거나 priority queue 사용

원문에서는 다른 풀이를 참고했고, queue로는 왜 안 되는지 고민하다가 높이가 큰 순서대로 처리하는 heap 방식을 구현했다. 이번에는 같은 원리를 더 직접적으로 드러내는 top-down 풀이로 다시 정리했다.

DP 상태와 종료 조건

paths(row, column)을 현재 칸에서 목적지까지 내려가는 경로의 수라고 정의한다.

paths(r, c)
= Σ paths(nr, nc)
  단, map[nr][nc] < map[r][c]

목적지에 도착했다면 경로 하나를 완성한 것이므로 1을 반환한다. 아직 계산하지 않은 칸은 -1, 계산했지만 목적지로 갈 수 없는 칸은 0으로 구분한다. 이 구분이 없으면 경로가 0개인 칸을 매번 다시 탐색하게 된다.

Java 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static final int[] DR = {-1, 1, 0, 0};
    private static final int[] DC = {0, 0, -1, 1};

    private static int rowCount;
    private static int columnCount;
    private static int[][] height;
    private static int[][] memo;

    private static int countPaths(int row, int column) {
        if (row == rowCount - 1 && column == columnCount - 1) {
            return 1;
        }

        if (memo[row][column] != -1) {
            return memo[row][column];
        }

        memo[row][column] = 0;

        for (int direction = 0; direction < 4; direction++) {
            int nextRow = row + DR[direction];
            int nextColumn = column + DC[direction];

            if (nextRow < 0 || nextRow >= rowCount
                    || nextColumn < 0 || nextColumn >= columnCount) {
                continue;
            }

            if (height[nextRow][nextColumn] < height[row][column]) {
                memo[row][column] += countPaths(nextRow, nextColumn);
            }
        }

        return memo[row][column];
    }

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        rowCount = Integer.parseInt(tokenizer.nextToken());
        columnCount = Integer.parseInt(tokenizer.nextToken());
        height = new int[rowCount][columnCount];
        memo = new int[rowCount][columnCount];

        for (int row = 0; row < rowCount; row++) {
            tokenizer = new StringTokenizer(reader.readLine());
            Arrays.fill(memo[row], -1);

            for (int column = 0; column < columnCount; column++) {
                height[row][column] = Integer.parseInt(
                        tokenizer.nextToken()
                );
            }
        }

        System.out.println(countPaths(0, 0));
    }
}

왜 한 칸을 한 번만 계산해도 되는가

서로 다른 경로가 같은 칸에 도착하더라도 그 칸부터 목적지까지 가능한 선택은 같다. 출발 경로의 모양은 이후의 경로 수에 영향을 주지 않는다. 그래서 memo[r][c]를 재사용할 수 있다.

높이가 매번 엄격히 감소하므로 recursion 중 같은 상태를 다시 만나는 cycle도 없다. 각 칸은 최초 한 번만 네 방향을 확인하므로 시간 복잡도는 O(MN), memo와 recursion stack을 포함한 공간은 최악 O(MN)이다.

당시 풀이에서 남은 것

원문에는 자력으로 끝까지 도출한 풀이가 아니라 다른 사람의 풀이를 참고했다고 분명히 적혀 있다. queue가 왜 맞지 않는지 생각하다 “높이가 큰 칸부터 처리하면 되지 않을까”라는 데 도달해 priority queue 방식으로 구현했다.

그 생각은 유효했다. 엄격히 낮아지는 이동은 높이 자체가 topological order 역할을 하기 때문이다. 다만 중복 삽입과 처리 순서를 직접 관리하는 대신 DFS memoization을 쓰면 “한 칸 이후의 경로 수는 한 번만 계산한다”는 DP 상태가 더 선명하게 보인다.

일반 BFS의 거리 전파는 백준 7569 토마토, 구간을 나눠 같은 하위 문제를 재사용하는 DP는 백준 11066 파일 합치기에서 비교할 수 있다.

검증 범위

Java source를 수동 검토하고 1×1, 경로가 없는 grid, 여러 경로가 합류하는 grid와 작은 random grid를 높이 순서 bottom-up oracle과 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.