[Python] 백준 1520번 : 내리막 길

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

1520번: 내리막 길

---

💡 문제 풀이

그래프 탐색(DFS)에 DP를 곁들인 문제이다.

 

그냥 DFS로 구현하면 시간초과가 발생한다.

그래서 이미 지나온 길에 대해서는 이전에 방문한 결과를 바로 전달해 주는 방식으로 중간에 순회하는 시간을 줄일 수 있다.

✔️ 느낀 점

그냥 DFS 문제인 줄 알았지만 DP가 곁들인거 보고 큰코다쳤다.

💻 코드

import sys
input = sys.stdin.readline

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

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
cnt = 0

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

dfs(0,0)
print(cnt)

import sys
input = sys.stdin.readline

def dfs(x, y):
    if x == m-1 and y == n-1:
        return 1

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

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

print(dfs(0,0))