난이도 : 골드 3
유형 : DP
https://www.acmicpc.net/problem/1520

문제 접근

• (0, 0)에서 (M-1, N-1)까지 이동하는 경로의 수를 구하는 문제
• 단, 항상 현재 위치보다 낮은 곳으로만 이동 가능 (상하좌우)
• 단순 DFS로는 중복 방문이 너무 많아 시간 초과 → 메모이제이션이 필요한 DP + DFS 문제

핵심 아이디어

• DFS로 탐색하면서 경로 수를 dp[x][y]에 저장
• 이미 방문한 위치는 dp[x][y] != -1이면 재탐색하지 않음 → Top-down DP
• dp[x][y]는 (x, y)에서 (M-1, N-1)까지 이동 가능한 경로 수

해답 및 풀이

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

M, N = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(M)]

# dp[x][y] = (x,y)에서 도착지까지 가는 경로 수
dp = [[-1] * N for _ in range(M)]

# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y):
    if x == M - 1 and y == N - 1:
        return 1  # 도착지 도달 시 경로 1개

    if dp[x][y] != -1:
        return dp[x][y]  # 이미 계산된 경우

    dp[x][y] = 0  # 초기화

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]

        if 0 <= nx < M and 0 <= ny < N:
            if graph[nx][ny] < graph[x][y]:  # 더 낮은 지형만 이동 가능
                dp[x][y] += dfs(nx, ny)

    return dp[x][y]

print(dfs(0, 0))