[BOJ] 1502 내리막길 dfs + dp

문제 바로가기

import sys
from collections import deque
sys.setrecursionlimit(11111)
input = sys.stdin.readline

h, w = list(map(int, input().split()))
dots = [[0 for _ in range(w)] for _ in range(h)]
nums = []
for _ in range(h):
    nums.append(list(map(int, input().split())))

def find(cur): # 현재위치
    x,y = cur
    if cur == (h-1,w-1):
        dots[x][y] += 1
        return 1
    if dots[x][y] > 0:
        dots[h-1][w-1] += dots[x][y]
        return dots[x][y]
    if dots[x][y] < 0:
        return -1
    for i,j in [(x-1,y),(x,y-1),(x+1,y),(x,y+1)]:
        if 0<= i < h and 0 <= j < w and nums[x][y] > nums[i][j]:
            k = find((i,j))
            if k > 0:
                dots[x][y] += k
    if dots[x][y] == 0:
        dots[x][y]= -1
    return dots[x][y]

find((0,0))
print(dots[-1][-1])

처음엔 쉬운 문제인줄 알았는데..! 생각보다 시간 제한이 까다로웠다.
dfs 에 dp 까지 추가해야 문제를 풀 수 있었다.
nums 에는 문제에서 주어진 각 지점의 높이를 저장하고
dots 에는 해당 점에서 끝 점까지 갈 수 있는 경우의 수를 저장한다.

단순히 경우의 수만 저장해도 시간초과였다..! 추가로 끝점까지 갈 수 있는 경우의 수가 없는 경우에는 dots 에 -1을 저장하여 더 이상의 탐색을 중단하게 하였다.