내리막 길[백준 1520] - python

import sys
input = sys.stdin.readline

def BOJ1520() :
  global M, N
  global l
  directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
  
  def get_load(dp, curr_x, curr_y):
    
    if curr_x == M - 1 and curr_y == N - 1 :
      return 1
    if dp[curr_x][curr_y] != -1 :
      return dp[curr_x][curr_y]
    
    dp[curr_x][curr_y] = 0
    for dir_x, dir_y in directions :
      next_x = curr_x + dir_x
      next_y = curr_y + dir_y
      if 0 <= next_x < M and 0 <= next_y < N and l[next_x][next_y] < l[curr_x][curr_y] :
        dp[curr_x][curr_y] += get_load(dp, next_x, next_y)
    return dp[curr_x][curr_y]

  M, N = map(int, input().split())
  l = []
  for _ in range(M) :
    l.append(list(map(int, input().split())))
  
  dp = [[-1 for _ in range(N)] for _ in range(M)]
  print(get_load(dp, 0, 0))
  

BOJ1520()



접근방법: 

1. dp 배열은 해당 지점에서 목적지까지 가는 방법의 수이다. 문제를 해결하기 위해 dfs + dp를 이용하였다.

2. dp 배열을 -1로 초기화 시켜주었다. 아직 방문하지 않았다는 의미를 나타낸다.

3. 탐색을 시작할때 시작점을 0으로 초기화 시켜준다. 

0으로 초기화 시켜주는 것은 memoization을 사용하기 위함인데, 이는 같은 길을 또 다시 탐색하는 경우를 방지하기 위함이다.

 

dfs에서 길을 탐색중에 만약 -1이 아닌 0의 값을 가진 지점을 방문했다면 해당 지점에서 목적지까지 가는 경로는 없다는것을 의미한다.

(문제를 풀 당시에 0으로 초기화 시켜주지 않아 계속 시간초과가 발생하였었다)

방문 지점이 0이면 해당 지점을 통한 경로는 더 이상 탐색하지 않아도 된다.

 

재귀 함수에서 목적지를 만났을때 1을 반납, 

방문하지 않은 지점을 만나면 계속 탐색하고 방문했던 지점이라면 해당 지점의 값을 반납해주면 된다.

 

아직 방문하지 않은 지점과 방문했지만 경우의 수가 0인 경우를 나누어서 다루는 것이 핵심이었던 것 같다.

 

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

1520번: 내리막 길