[백준] BOJ_1520 내리막 길

이종찬·2026년 1월 19일

1. 문제 정보

문제 요약: $M \times N$ 격자 지도에서 각 칸의 높이가 주어집니다. 제일 왼쪽 위 칸에서 제일 오른쪽 아래 칸으로 이동하되, 반드시 높이가 더 낮은 지점으로만 이동할 수 있는 경로의 개수를 구하는 문제입니다.
핵심 제약: $M, N \le 500$ , 높이 $\le 10,000$ .
난이도: Gold III
원본 링크: 백준 1520 - 내리막 길

2. 접근 방식

1) 문제의 본질 (분석)

이 문제의 핵심은 "이동 조건"에 있습니다. 항상 현재 칸보다 낮은 칸으로만 이동해야 한다는 조건은 이 그래프가 순환 의존성(Cycle)이 없는 DAG(Directed Acyclic Graph)임을 보장합니다.

단순히 모든 경로를 탐색하면 되는 것처럼 보이지만, 가능한 경로의 수가 기하급수적으로 많아질 수 있습니다. 따라서 일반적인 BFS나 단순 DFS로는 중복 계산이 발생하여 시간 초과(TLE) 또는 메모리 초과를 피할 수 없습니다.

2) 알고리즘 설계

중복 계산을 피하기 위해 Top-Down 방식의 DP를 설계합니다.

상태 정의: $DP[y][x]$ 를 위치에서 목적지 $(M, N)$ 까지 도달할 수 있는 경로의 수로 정의합니다.
방문 처리: 아직 방문하지 않은 칸(-1), 방문 중이거나 경로가 없는 칸(0)을 구분하여 Memoization을 수행합니다.
선형 환원: 각 칸에서의 탐색 결과를 재사용함으로써, 전체 시간 복잡도를 $O(M \times N)$ 으로 최적화합니다.

3) 점화식 및 수식

임의의 지점 $(y, x)$ 에서 인접한 네 방향의 좌표를 $(ny, nx)$ 라고 할 때, 다음 조건을 만족하는 경로의 합이 해당 지점의 결과값이 됩니다.

$DP[y][x] = \sum_{i=0}^{3} DP[ny][nx] \quad (\text{단, } A[y][x] > A[ny][nx] \text{ 이고 } (ny, nx) \text{가 범위 내일 때})$

4. 코드 구현

❌ 실패한 코드 (BFS 방식)

이 코드는 중복된 경로를 큐에 모두 담으려 시도하여 메모리 초과 또는 시간 초과가 발생합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int M, N;
    static int[][] A;
    static int[] dy = {1, 0, -1, 0};
    static int[] dx = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        A = new int[M + 1][N + 1];
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{1, 1});
        int answer = 0;

        while (!q.isEmpty()) {
            int[] t = q.poll();
            int y = t[0];
            int x = t[1];

            if (y == M && x == N) {
                answer += 1;
            }

            for (int i = 0; i < 4; i++) {
                int ny = dy[i] + y;
                int nx = dx[i] + x;

                if (rangeMatch(ny, nx) && A[y][x] > A[ny][nx]) {
                    q.add(new int[]{ny, nx});
                }
            }
        }

        System.out.println(answer);
    }

    private static boolean rangeMatch(int ny, int nx) {
        return 1 <= ny && ny <= M && 1 <= nx && nx <= N;
    }
}

✅ 성공한 코드 (DFS + DP)

메모이제이션을 적용하여 각 노드를 단 한 번씩만 깊게 탐색하는 효율적인 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int M, N;
    static int[][] A;
    static int[][] dp;
    static int[] dy = {1, 0, -1, 0};
    static int[] dx = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        A = new int[M + 1][N + 1];
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dp = new int[M + 1][N + 1];
        for (int i = 0; i <= M; i++)
            Arrays.fill(dp[i], -1);

        int answer = dfs(1, 1);
        System.out.println(answer);
        
    }

    private static int dfs(int y, int x) {
        if (y == M && x == N) {
            return 1;
        }

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

        dp[y][x] = 0;

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (rangeMatch(ny, nx) && A[y][x] > A[ny][nx]) {
                dp[y][x] += dfs(ny, nx);
            }
        }

        return dp[y][x];
    }

    private static boolean rangeMatch(int ny, int nx) {
        return 1 <= ny && ny <= M && 1 <= nx && nx <= N;
    }
}

5. 회고 및 배운 점

시간 복잡도 분석

실패 원인 (BFS): BFS는 기본적으로 최단 거리를 찾기에는 좋으나, 이 문제처럼 '경로의 개수'를 찾는 경우 동일 지점을 각기 다른 경로로 여러 번 방문하게 됩니다. 최악의 경우 복잡도는 지수 시간( $O(4^{M \times N})$ )에 달할 수 있어 제한된 시간 내에 처리가 불가능합니다.
성공 분석 (DFS + DP): 메모이제이션을 사용하면 이미 계산된 지점은 즉시 반환되므로, 모든 격자 칸을 정확히 한 번씩만 방문하게 됩니다. 즉, $O(M \times N)$ 의 선형 시간에 수렴하여 약 250,000번의 연산만으로 해결 가능합니다.

구현 디테일

초기값 설정: dp 배열을 0이 아닌 -1로 초기화하는 것이 매우 중요합니다. 특정 지점에서 목적지까지 가는 경로가 실제로 0개인 경우와 아직 방문하지 않은 경우를 구분해야 중복 탐색을 완벽히 방지할 수 있기 때문입니다.
엣지 케이스: 인 경우나 모든 높이가 같아 이동이 불가능한 경우 등을 고려했을 때, DFS의 시작점에서 반환되는 값이 논리적으로 타당한지 검토가 필요합니다.