[DFS/DP] 백준 2146 파이썬 (내리막 길) 골드4

-풀이

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

#세로, 가로
M, N = map(int,input().split())
graph = []
for i in range(M):
  graph.append(list(map(int,input().split())))

dp = [[-1]*N for _ in range(M)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]

def DFS(x,y):
  #도착 지점에 도달하면 1(한가지 경우의 수)리턴
  if (x == (M-1)) and  (y == (N-1)):
    return 1

  #방문한 적이 있으면 그 위치에서 출발하는 경우의 수 리턴
  if dp[x][y] != -1:
    return dp[x][y]  
  
  count = 0
  
  for i in range(4):
    nx = x + dx[i]
    ny = y +dy[i]
    if 0 <= nx < M and 0 <= ny < N and graph[x][y] > graph[nx][ny]:
      count += DFS(nx, ny)
  dp[x][y] = count
  return dp[x][y]

print(DFS(0,0))

-풀이설명

처음에 DFS로 풀 수 있을 줄 알고 풀었는데, 시간초과가 떴다. 풀이를 조금 찾아보니 최대 500x500크기의 경우의 수를 찾는 것은 굉장히 많다는 사실을 알게되었다.

결국 풀려면 DFS와 DP를 이용하여 풀어야 했다. DP쪽에 많이 약해서 풀이를 보고 이해하며 코딩하기가 조금 버거웠다. 다시 이런 비슷한 문제가 나온다면 풀 수 있을지 확신할 수는 없을 것 같다. 복습 자주 할 것.

원리는 도착지점이 아닌 지점에서 도착지점 까지의 경우의 수를 모두 합한 것을 구하는 것이 도착 지점까지의 경우의 수가 된다.

-풀이 참고 출처:https://studyandwrite.tistory.com/387