[Python] 백준 1520번 - 내리막 길, 다이나믹 프로그래밍-기초

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

1520번: 내리막 길

문제요약:

dfs와 메모이제이션을 활용하여 총 경로의 수를 출력한다

 

생각의 흐름:

모든 내리막길로 가봐야겠네! -> 그런데 시간이 너무 걸릴 것 같은데? ->

이미 방문한 곳은 메모이제이션해서 방문하지 말자

import sys
 
dx = [1, 0, -1, 0] ## 상하좌우를 나타낸다
dy = [0, 1, 0, -1]
sys.setrecursionlimit(10000) ## 파이썬의 기본 재귀 깊이는 1000밖에 되지 않으므로 늘려준다 
 
y_lis, x_lis = map(int, sys.stdin.readline().split()) ## 빠른 input으로 데이터를 받아준다
array = []
dp = [[0 for _ in range(x_lis)] for _ in range(y_lis)]; dp[y_lis - 1][x_lis - 1] = 1 ## 도착 지점에 1을 표시한다
## 이후 재귀를 돌면 dp[0][0]에 총 갈 수 있는 경로의 수가 나올 것이다
visited = [[0 for _ in range(x_lis)] for _ in range(y_lis)]; ## 방문 여부를 표시한다
for i in range(y_lis): array.append(list(map(int, sys.stdin.readline().split()))) ## 데이터를 입력받는다
 
def dfs(y, x): ## 깊이 우선 탐색
    for i in range(4):
        ny = y + dy[i] ## 상하좌우로 옮겨간 위치를 표시한다
        nx = x + dx[i]
        if (ny < 0 or ny >= y_lis or nx < 0 or nx >= x_lis): continue ## 범위 제한
        if array[ny][nx] >= array[y][x]: continue ## 문제 규칙
        if not dp[ny][nx]: ## dp가 초기화 되지 않았다면
            if not visited[ny][nx]: dfs(ny, nx) ## 방문하지 않았다면 더 깊이 탐색한다
            dp[y][x] += dp[ny][nx] ## 메모이제이션한 값을 추가 한다
            visited[ny][nx] = True ## 방문여부
        else:
            dp[y][x] += dp[ny][nx] ## 메모이제이션한 값을 추가 한다
dfs(0, 0)
print(dp[0][0])