백준 - 내리막길 (1520)

문제 링크 ▶︎ 백준 내리막길 1520

문제 전략

이 문제는 DFS로 푼 문제이다.
(0,0)에서 출발하여 (n-1,m-1)까지 이동하는 과정에서 조건을 만족하면 재귀함수를 호출하는 구조이다.

dfs(n-1,m-1) 의 값은 1을 리턴하며,
재귀함수 진행이 완료되면 이전 호출로 돌아오며 k 에 더해준다.
k는 visit의 해당 좌표값이 되고 즉, 해당 좌표를 통과하는 경로의 수를 의미한다.

코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

m, n = map(int,input().split()) # m행 n열
maps = [list(map(int,input().split())) for _ in range(m)]
visit = [[-1] * n for _ in range(m)]
cnt = 0
dx = [1,0,-1,0]
dy = [0,-1,0,1]

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

print(dfs(0,0))

개선 사항

생각하면 할수록 어려운 문제.