[Baekjoon] 1520번 내리막 길 / Python

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

1520번: 내리막 길

생각한 풀이과정

• DFS와 DP(코드 내 visited 함수)를 사용하여 해결한 문제
• 항상 높이가 낮은 지점으로 간다는 말에 초점을 맞춰야 함
• 마지막 지점 도달할 경우 return 1 = 실행대기중인 함수들을 통한 경로 개수 증가

제출 시 주의사항

• 생각보다 재귀를 많이 돈다. sys.setrecursionlimit 사용

import sys
sys.setrecursionlimit(100000)

n, m = map(int, sys.stdin.readline().split())
maps = []
for i in range(n) :
    maps.append(list(map(int, sys.stdin.readline().split())))

visited = [[-1] * m for _ in range(n)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def dfs(x, y) :
    #  제일 오른쪽 아래 지점까지 항상 내리막길로만 이동
    if x == n - 1 and y == m - 1 :
        return 1
    if visited[x][y] != -1 :
        return visited[x][y]
    visited[x][y] = 0
    # 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능
    for i in range(4) :
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and nx < n and ny >= 0 and ny < m :
            if maps[x][y] > maps[nx][ny] : # 항상 높이가 더 낮은 지점으로만 이동
                visited[x][y] += dfs(nx, ny)
    return visited[x][y]

# 제일 왼쪽 위 지점에서 출발
print(dfs(0,0))