1520 - 내리막 길

info

• 문제 보기: 1520 - 내리막 길
• 소요 시간: 17분 21초
• 풀이 언어: python
• 체감 난이도: 2️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

DP

풀이 코드

info

• 메모리: 47596 KB
• 시간: 124 ms

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

y, x = 0, 0
table, memo, visited = [], [], []

def dp(i, j):
    if i == y-1 and j == x-1:
        return 1
        
    if ~memo[i][j]:
        return memo[i][j]
    
    res = 0
    cur_val = table[i][j]
    visited[i][j] = True
    
    if j+1 < x and cur_val > table[i][j+1] and not visited[i][j+1]:
        res += dp(i, j+1)
    if i+1 < y and cur_val > table[i+1][j] and not visited[i+1][j]:
        res += dp(i+1, j)
    if i-1 > -1 and cur_val > table[i-1][j] and not visited[i-1][j]:
        res += dp(i-1, j)
    if j-1 > -1 and cur_val > table[i][j-1] and not visited[i][j-1]:
        res += dp(i, j-1)
    
    visited[i][j] = False
    
    memo[i][j] = res
    return res
    

def solution():
    global y, x, table, memo, visited
    y, x = map(int, input().split())
    for _ in range(y):
        table.append(list(map(int, input().split())))
    
    memo = [[-1 for _ in range(x)] for _ in range(y)]
    visited = [[False for _ in range(x)] for _ in range(y)]
    
    print(dp(0, 0))


if __name__ == '__main__':
    solution()

풀이 해설

격자모양 + 완탐 + 중복계산최적화

를 떠올리게 하는 점에서 DP 문제임을 의심해볼 수 있다. 이 때 문제에서

각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

라고 설명하였으므로, DP의 진행 방향은 4방향이다.

다만 상하좌우 이동 특성 상 이미 지나온 곳을 또 재방문할 수 있기 때문에,
이를 visited 처리하여 재방문하지 않도록 처리해야 한다.

또한 이동 경로의 모양마다 visited 처리는 분리된다.

따라서 $dp(i, j)$의 정의가 $(i, j)$에서의 경로 개수이므로,
이미 계산된 $dp(i, j)$는 다른 모양의 경로를 계산할때 해당 좌표 방문 시 재사용할 수 있다.

이를 메모이제이션하여 최적화하면 끝~

📌Return Value의 분기

def dp(i, j):
    if i == y-1 and j == x-1:
        return 1
        
    if ~memo[i][j]:
        return memo[i][j]
    
    res = 0
    cur_val = table[i][j]
    visited[i][j] = True
    ...

#️⃣ Line 2

$(i, j)$가 지도의 우측 하단 끝이라면, 목표 지점에 도착한 것이므로 경로 하나를 발견했다는 의미로 return 1 처리한다.

#️⃣ Line 8

만약 $(i, j)$를 통하는 경로가 목표 지점에 도달하지 못한다면 경로 개수는 0이어야 하므로, res의 초기값은 0이 되어야 한다.

나머지는 늘...뭐... 맨날 먹던 맛...

메모

• 또 setrecursionlimit 까먹어서 원트컷 실패함;

😐...