[백준 1520 / Python] 내리막 길

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

1520번: 내리막 길

각 칸에 그 지점의 높이가 쓰여 있고, 각 지점의 이동은 상하좌우 이웃한 곳끼리만 가능하다.
제일 왼쪽 위칸에서 제일 오른쪽 아래칸으로 가는데 항상 높이가 더 낮은 지점으로만 이동하는 경우의 수를 구하자.

 

접근 방식

DP를 이용해 지나갈때마다 방문표시를 해 그 지점에 카운트를 시키며 지나가 마지막 경로에 도착시 1을 리턴하며 시작점 DP값에 증감시켜 경우의 수를 구한다.

DFS를 이용해 상화좌우 리스트로 인접한 지점과 항상 높이가 더 낮은지점으로만 이동하게 한뒤 조건이 맞으면 DP값에 DFS 재귀를 돌게 구현한다.

풀이 코드

import sys
input = sys.stdin.readline

def dfs(x,y):

    if x ==m-1 and y==n-1: # 도착지점에 왔다면 1 리턴
        return 1

    if dp[x][y]==-1: #이동시마다 0으로 방문설정
        dp[x][y]=0

        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<m and 0<=ny<n and map[x][y]>map[nx][ny]:
                dp[x][y]+=dfs(nx,ny)

    return dp[x][y] # 방문칸일때 dp값 리턴




m,n = map(int,input().split())
map = [list(map(int,input().split())) for _ in range(m)]
dp = [[-1]*n for _ in range(m)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]

print(dfs(0,0))