[백준1520&파이썬] DFS에 메모이제이션을 곁들여서 시간초과를 해결하자

# 문제

백준 1520 내리막길 파이썬 풀이

1520번: 내리막 길

 

# 코드

## 성공한 코드

import sys


M, N = map(int,sys.stdin.readline().split()) # M : 행 , N : 열

board = list()
memo = [ [-1] * N for _ in range(M)]

for _ in range(M) :
  line = list(map(int,sys.stdin.readline().split()))
  board.append(line)


dirs = [
  (-1,0), (0,1), (1,0), (0,-1)
  ]

def printBoard(board) :
  for i in range(len(board)) :
    for j in range(len(board[i])) :
      print(board[i][j],end=" ")
    print()

target = (M-1, N-1)
def dfs(r,c) :
  if r == target[0] and c == target[1] :
    return 1

  if memo[r][c] >= 0 :
    return memo[r][c]

  checker = 0
  for dir in dirs :
    next = (r + dir[0], c + dir[1])
    if 0<= next[0] < M and 0<= next[1] < N : # 범위 체크


      if board[next[0]][next[1]] < board[r][c] :
        checker += dfs(next[0],next[1]) # 다음칸으로 이동


  memo[r][c] = checker

  return checker

dfs(0,0)
# printBoard(memo)
print(memo[0][0])

## 시간초과 코드

##### ----- 시간초과 ----- #####
def dfs(r,c) :
  global cnt
  if r == target[0] and c == target[1] :
    cnt+=1
    return

  for dir in dirs :
    next = (r + dir[0], c + dir[1])
    if 0<= next[0] < M and 0<= next[1] < N : # 범위 체크
      if board[next[0]][next[1]] < board[r][c] :
        dfs(next[0],next[1]) # 다음칸으로 이동

dfs(0,0)
print(cnt)

##### ----- ----- ----- #####

 

# 풀이

## DFS를 통한 목표지점에 도달했으나 시간초과

• 재귀식을 구성하고, DFS를 이용해 목표지점까지의 도달조건에 따라서 코드를 작성했으나 시간초과가 났다.
• 모든곳을 탐색해야하기 때문에 시간이 오래걸린다. 
• 한번 탐색을 마친곳은 재탐색하지 않고 그곳의 정보를 다시 사용하는 방법에 대해서 고민까지 연결 됐다.

## 메모제이션을 곁들이자

• DFS 풀이의 시간초과를 해결하기 위해서 DP(+메모이제이션)를 곁들이는 풀이방법이 자주쓰이는 방법 같다.
• 재귀식을 통해서 끝지점까지 도달하고 이걸 리턴 1 시키고, 반복문을 토대로 해당 위치에서 4방향의 총 합을 구한다.
• 메모제이션 방식과 유사하게 재활용하여, 끝까지 계산하지 않도록 한다. 

## 0의 정보를 무시하지 말자

• 난 visit를 표시하는 memo배열을 만들때 초기값을 0으로 설정했다.
• 그리고 1이상인 경우에만 메모이제이션을 활용하도록 했다.
• 그러나 0도 정보이다. 0이라는 확정된 정보가 있다면 굳이 끝까지 가지 않아도 된다.
• 초기값을 -1로 재설정해주면 된다.

## 다음 위치를 예상하는 주접을 떨지말고, 현재위치 기준으로 memo를 판단해라

• bfs문제를 풀때 다음 위치를 기준으로 잡다보니까, 여기서 자꾸 틀렸다.