백준 1520 : 내리막 길 [파이썬]

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

1520번: 내리막 길

1. 문제 설명

DFS + DP를 이용한 문제이다.

DFS로만 푼다면 모든 경우의 수를 다 세야 하기 때문에 많은 경우의 수가 나오게 된다.

그래서 DP를 이용해서 불필요한 연산을 줄여야한다.

도착 지점까지 가는 경우의 수는 도착 지점이 아닌 임의의 점들에서 도착지점까지 가는 경우의 수를 합한 것과 같음

2. 코드

import sys
input = sys.stdin.readline

def dfs(x, y):
    # 도착 도달하면 1을 리턴
    if x == n-1 and y == m-1:
        return 1

    # 이미 방문한 적이 있다면 그 위치에서 출발하는 경우의 수를 리턴
    if dp[x][y] != -1:
        return dp[x][y]
    
    ways = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0<=nx<n and 0<=ny<m and graph[x][y] > graph[nx][ny]:
            ways += dfs(nx, ny)
    
    dp[x][y] = ways
    return dp[x][y]

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

print(dfs(0,0))

• 시작 지점에서 출발해서 DP 테이블이 갱신되지 않은 곳(X)을 만난다면,
• 해당 지점(X)부터 도착 지점까지 갈 수 있는 경로의 수를 그곳에 업데이트 한다.
• X지점의 DP 테이블이 이미 갱신되어 있다면, 그 곳이 부분 최적해가 되므로 그 값을 그대로 전체 정답에 더해준다.