백준 1520번 - 내리막길

내리막길 문제 바로 가기

풀이 날짜: 2026-04-11

baekjoon 알고리즘 문제 풀이

풀이 코드


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**4)

n,m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
dp = [[-1]*m for _ in range(n)]

dx = [0,0,-1,1]
dy = [-1,1,0,0]

def dfs(x,y):
    if x == n-1 and y == m-1:
        return 1
    
    if dp[x][y] != -1:
        return dp[x][y]
    
    dp[x][y] = 0
    
    for i in range(4):
        nx = dx[i] + x
        ny = dy[i] + y

        if 0<=nx<n and 0<=ny<m:
            if graph[nx][ny] < graph[x][y]:
                dp[x][y] += dfs(nx,ny)
    
    return dp[x][y]

print(dfs(0,0))

접근 방법

단순한 DFS나 BFS로 풀려고 하면 시간 초과가 발생하는 대표적인 문제이다. 처음에는 시작점에서 도착점까지 이동 가능한 모든 경로를 DFS로 탐색하려고 했지만, 동일한 위치에서 시작하는 경로가 여러 번 반복 계산되는 문제가 발생했다. 따라서 이 문제는 단순 DFS가 아니라 DFS + DP(메모이제이션) 방식으로 접근해야 한다.

핵심 아이디어

먼저 DFS 함수의 의미를 명확하게 정의해야 한다. 여기서 dfs(x, y)는 좌표 (x, y)에서 출발하여 도착점 (n-1, m-1)까지 갈 수 있는 내리막 경로의 개수를 의미한다. 즉, 단순히 이동이 가능한지 여부를 판단하는 것이 아니라, 해당 위치에서 시작했을 때 도착점까지 이어지는 모든 가능한 경로의 수를 반환하도록 설계하였다.

도착점에서 return 1을 하는 이유

1을 반환하는 이유는 도착점에 도달한 하나의 완성된 경로를 의미하기 때문이다. 예를 들어 어떤 위치에서 도착점으로 이동할 수 있다면, 그 경로는 하나의 유효한 경로로 인정된다. 만약 여기서 0을 반환한다면 도착점에 도달한 경우조차 경로로 인정되지 않기 때문에 모든 계산 결과가 0이 되어버린다. 따라서 도착점은 하나의 경로를 완성하는 지점이므로 1을 반환해야 한다.

경로 개수를 누적하는 방식

현재 위치에서 이동할 수 있는 방향은 상하좌우 네 방향이며, 반드시 현재 위치보다 높이가 낮은 칸으로만 이동할 수 있다. 조건을 만족하는 다음 위치 (nx, ny)가 있다면 그 위치에서 도착점까지 갈 수 있는 경로의 수를 재귀적으로 계산한다.

메모이제이션(DP)을 사용하는 이유

이 문제는 겉보기에는 그래프 탐색 문제처럼 보이지만 실제로는 DP 기반의 경로 계산 문제에 가깝다. DFS는 경로를 탐색하는 역할을 하고, DP는 중복 계산을 방지하는 역할을 한다. 즉, DFS를 이용해 가능한 이동을 탐색하면서 동시에 DP 배열을 이용해 이미 계산한 결과를 저장하고 재사용하는 방식이다. 이러한 구조를 흔히 DFS + Memoization 또는 Top-down DP라고 부른다.

DFS + DP 구조의 특징

다익스트라 한 번만 돌리면 된다고 착각함
distance를 전역으로 두고 재사용하려고 했음
i → X를 구하는 방법을 몰랐음

Vienna sausage