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

📌문제 출처

백준 단계별 문제풀이 - 동적 계획법 2
https://www.acmicpc.net/problem/1520

1520번: 내리막 길

❓ 문제

❗ 풀이

• dp + dfs

📗 풀이 코드

import sys
from collections import deque
input = sys.stdin.readline

# dfs 함수 생성
def dfs(row,col):
    if (row==m-1) and (col==n-1) : # 도착했을 경우
        return 1
    
    if dp[row][col] != -1 : # 방문한 적 있을 경우
        return dp[row][col] # 더이상 진행하지 않고 해당 경로에서 가능한 경로 수를 반환
    
    cnt = 0 # 해당 칸에서 도착 가능한 모든 경로의 수를 담는다.
    for i in range(4): # 상하좌우 이동
        nrow,ncol = row+drow[i], col+dcol[i] # 이동할 칸 초기화
        if 0<=nrow<m and 0<=ncol<n and maps[row][col] > maps[nrow][ncol]: # 이동가능하면
            cnt += dfs(nrow,ncol) # dfs 진행한 결과 중 도착 가능한 수를 담음
    dp[row][col] = cnt
    return dp[row][col] # 해당 칸에서 모든 확인이 끝났다면 해당 칸에서 도착 가능한 경로 수를 반환

m,n = map(int,input().split())
maps = [list(map(int,input().split())) for _ in range(m)]
dp = [[-1]*n for _ in range(m)] # 0으로 해주면 도착 가능 경로 수가 0회인 곳과 미방문 지역을 구분 불가
drow,dcol = [-1,1,0,0], [0,0,-1,1]
print(dfs(0,0))

📗 코드 해설

• dfs나 bfs만 사용했을 때는 시간 초과 발생
• 현재 있는 칸에서 상하좌우를 방문하는 네 경우에서 골인가능한 경우의 수를 더해준다.
• dfs가 깊어져 골인 지점에 도착하면 1을 반환하고 이 1은 한 단계 위의 dfs 함수의 반환값이 되며
  한 단계 위에서 dfs가 시작된 칸에서는 상하좌우의 다른 dfs에서 반환되는 숫자 또한 합해준다.
• 이미 방문한 곳은 다시 방문하지 않고 해당 칸의 정보만 가져와서 반복 방문을 줄이자.
• dp는 0이 아닌 -1로 시작하는데, 0으로 대입해주면 도착 가능 경로 수가 0인 곳과 미방문 지역을 구분하지 못하기 때문