[BOJ] 1520 내리막 길_DP, DFS

내리막 길

link

풀이

• 방식 : DP, DFS
• 내리막길로 일방통행만 가능함
• DFS로 가장 깊은 node에 도착 후 dp에 가능 경로의 수를 Update하여 Return
• 그러다가 이전에 만났던 node에 도착하면 그 값을 Return하여 다시 반복하는 경우를 줄여줌

📰code

import sys
input = sys.stdin.readline
sys.setrecursionlimit(250000)

n,m = list(map(int,input().split()))
hill = [list(map(int,input().split())) for _ in range(n)]

dp = [[-1]*m for _ in range(n)]
move = [(1,0),(-1,0),(0,1),(0,-1)]
dp[n-1][m-1] =1

def dfs(x,y):
    if dp[y][x] != -1: # 이미 들렸던 Node를 제거해줌
        return dp[y][x]
    dp[y][x] = 0
    for dx,dy in move:
        if 0<=x-dx<m and 0<=y-dy<n and hill[y][x] > hill[y-dy][x-dx]:
            dp[y][x] += dfs(x-dx,y-dy) # update DP
    return dp[y][x]
dfs(0,0)
print(dp[0][0])

틀렸던 풀이 이력

• dp에 0을 넣어 추가하는 방식으로 진행
• 이미 지나갔지만 방법이 없어서 0으로 update 된 point를 반복하여 탐색하기 때문에 시간 Loss가 발생함

📰code

####### 함수부분 #######
dp = [[0]*m for _ in range(n)]
move = [(1,0),(-1,0),(0,1),(0,-1)]
dp[n-1][m-1] =1

def dfs(x,y):
    for dx,dy in move:
        if 0<=x-dx<m and 0<=y-dy<n and hill[y][x] > hill[y-dy][x-dx]:
            if dp[y-dy][x-dx] != 0:
                dp[y][x] += dp[y-dy][x-dx]
            else : dp[y][x] += dfs(x-dx,y-dy)
    return dp[y][x]

💡 수정 필요한 내용은 댓글이나 메일로 알려주시면 감사하겠습니다!💡