알고리즘/백준
[백준] 1520번 내리막 길 (파이썬)
알감자
2022. 1. 4. 20:11
1520번: 내리막 길
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으
www.acmicpc.net
코드
import sys
m, n = map(int, sys.stdin.readline().split(" "))
check_li = [[-1 for _ in range(n)] for _ in range(m)]
li = []
for _ in range(m):
li.append(list(map(int, sys.stdin.readline().split(" "))))
x_ext_li = [0,0,1,-1]
y_ext_li = [1,-1,0,0]
def dfs(node):
x, y = node
if x == m-1 and y == n-1:
return 1
if check_li[x][y] != -1:
return check_li[x][y]
check_li[x][y] = 0
for i in range(4):
x_ext = x + x_ext_li[i]
y_ext = y + y_ext_li[i]
if 0 <= x_ext < m and 0 <= y_ext < n:
if li[x_ext][y_ext] < li[x][y]:
check_li[x][y] += dfs([x_ext, y_ext])
return check_li[x][y]
print(dfs([0,0]))