[백준] 1520

내리막길 (1520번)

• 사이트/난이도: 백준/골드3
• 코드

# 골드3 내리막 길
# dp + dfs
import sys
input = sys.stdin.readline

m, n = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(m)]
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
    if dp[x][y] != -1:
        return dp[x][y]

    result = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < m and 0 <= ny < n and graph[nx][ny] < graph[x][y]:
            result += dfs(nx, ny)
    dp[x][y] = result
    return dp[x][y]
       

print(dfs(0, 0))

• 느낀점
  • dp + dfs 문제
  • 그래프의 가로, 세로 길이가 500이므로 dfs 만을 이용하면 시간초과가 난다.
  • dp를 이용하기 위해서는 부분문제로 쪼갤수 있는지 확인해야 되는데,
  • 임의의 점에서 도착지점까지의 경우의수를 안다면 어떤 점이 임의의 점까지 도착만 한다면 그 이후의 경로는 구할 필요가 없으므로 쪼갤수 있다.
  • 즉, 도착 지점까지 가는 경우의 수는 임의의 점에서 도착지점까지의 경우의 수를 합한 것과 같다.