[Python 3] BOJ - 1520 "내리막 길"

 #문제 링크 : https://www.acmicpc.net/problem/1520

1520번: 내리막 길

 # 풀이 :

개인적으로 이 문제는 DP문제라고 생각한다. 이 문제를 풀 때 단순히 BFS, DFS를 하게 되면 같은 정점을 계속 방문하게 되므로 시간초과 및 메모리초과를 피할 수 없기 때문이다. BFS와 Bottom-Up DP로 풀수도 있고 DFS와 Top-Bottom DP로도 풀 수 있으니 취향에 따라 접근하면 되지만 이번 포스팅에서는 DFS와 Top-Bottom DP로 포스팅하겠다

 왜 이 문제가 DP냐면 높이가 높은쪽에서 낮은 쪽으로 이동하면 낮은 쪽에서 높은 쪽으로는 갈 수 없으므로 문제의 크기가 줄어들고 (i+1,j+1)위치로 갈 때 (i+1,j), (i-1,j), (i, j-1), (i,j+1)의 네 방향의 가짓수가 연속해서 (i+1, j+1)의 가짓수에 영향을 미치기 때문이다. 문제에서 불가능한 경우에 대한 특별한 언급이 없으므로 최소 1개의 경로는 도착점으로 내리막길을 이용하여 도착할 수 있으므로 Base Case에 1을 리턴하도록 한다

 

 # 코드

import sys
sys.setrecursionlimit(10 ** 9)

# 입력부
n, m = map(int, sys.stdin.readline().split())
mountain = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

# dp : (i,j)로 갈 수 있는 경우의 수를 담는 2차원 배열
dp = [[-1] * m for _ in range(n)]

# dx, dy : 방향배열
dx = [0,0,1,-1]
dy = [1,-1,0,0]

# dfs : dp배열에 따라 도착점의 경우의 수를 리턴하는 함수
def dfs(x,y):
    # base case이므로 1리턴
    if x == n - 1 and y == m - 1:
        return 1
    # 이미 방문한 정점이라면 dp값 리턴
    if dp[x][y] != -1:
        return dp[x][y]
    # 처음 방문한 정점이라면 0으로 초기화
    dp[x][y] = 0
    # dfs 탐색
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if mountain[nx][ny] < mountain[x][y]:
                # 점화식
                dp[x][y] += dfs(nx, ny)
    return dp[x][y]

# 정답 출력
print(dfs(0,0))