[ 백준 1520번 내리막 길 ] Python 코드 (메모이제이션 a.k.a. DP)

1. 문제

https://www.acmicpc.net/problem/1520

1520번: 내리막 길

---

2. 리뷰

어떻게 DP문제는 풀 때마다 새롭다.

이것도 DP로 풀 수 있다고?라는 충격의 연속이다.

특히 이 문제는 Top-Down 방식의 메모이제이션만이 DP에 비해 차별화된 강점을 보여주었다.

지금까지 푼 문제들은 DP와 메모이제이션이 상호변환이 가능했는데, 이 문제는 DP로는 풀기 어려웠다.

(솔직히 불가능하다고 생각하지만 혹시 모르니까....ㅎㅎㅎ)

 

문제를 보면 가장 먼저 DFS가 떠오른다.

하지만 안타깝게도 DFS로 풀면 시간초과가 발생한다.

왜냐하면 단순히 노드의 완전탐색이 아닌, 경로의 수를 계산해야하기 때문에

노드의 중복 방문을 허용하기 위해서 visited배열을 제거하였고, 이는 시간복잡도를 기하급수적으로 높였다.

 

완전탐색을 하기는 해야할텐데 시간초과가 나버리니 자연스레 DP를 생각했다.

그런데 이 문제는 하나의 Problem을 상,하,좌,우 4방향의 Subproblem으로 나눈다.

지금까지는, DP배열 상에서 Subproblem들이 Problem의 한쪽으로 치우쳐 있었다.(예를 들어, 좌측 혹은 좌상측)

그렇기 때문에 적절한 탐색순서를 정해 Bottom-Up방식으로 DP배열을 채워나갈 수 있었다.

그런데 상, 하, 좌, 우 4방향에서 DP배열을 채워나가야한다면 탐색의 흐름을 정할 수 없다.

그렇기 때문에 Bottom-up방식으로 DP배열을 채울 수 없었고, 메모이제이션을 이용해야 했다.

 

---

3. DFS 풀이

솔직히 시간초과가 나서 아래 코드가 확실히 맞다!! 라고는 말할 수 없다.

그냥 '이 사람은 이런 식으로 생각했구나'하고 보면 좋을 것 같다.

# 1. DFS 시간초과
N, M = map(int, input().split())
arr = [[10001] * (M + 2)] + [[10001] + list(map(int, input().split())) + [10001] for _ in range(N)] + [[10001] * (M + 2)]

stk = []
stk.append((1, 1))

cnt = 0
while stk:
    i, j = stk.pop()
    if i == N and j == M:
        cnt += 1
        continue
    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni = i + di
        nj = j + dj
        if arr[ni][nj] < arr[i][j]:
            stk.append((ni, nj))

print(cnt)

 

---

4. 메모이제이션 풀이

DP배열에 대한 메인아이디어는 다음과 같다.

1. DP[i][j]에 저장되는 값은 시작지점부터 arr[i][j]까지의 경로 수이다.
2. Problem DP[i][j]는 4개의 Subproblems DP[i+1][j], DP[i-1][j], DP[i][j+1], DP[i][j-1]으로 나눌 수 있다.
   왜냐하면 arr[i][j]에 접근하기 위해서는 반드시 arr[i+1][j], arr[i-1][j], arr[i][j+1], arr[i][j-1] 4방향 중 하나를 통과해야하기 때문이다. 그리고 문제조건 상, arr[i][j] < arr[ni][nj]일 경우에만 DP[i][j]+=DP[ni][nj]해준다.

DP를 4방향으로부터 계산해야하기 때문에 DP배열의 계산 순서를 정할 수 없어,

Top-Down 방식의 메모이제이션으로 구현했다.

단순히 계산방식을 Bottom-Up에서 Top-Down으로 바꾼 것이기 때문에 메인아이디어가 다르지는 않다.

단, 밑에 코드에서는 편의상 DP배열의 이름을 memo로 바꿔서 작성했다.

N, M = map(int, input().split())
# 아래의 for문 안 if문에서 ni, nj가 arr범위 안에 있는지 확인하는 조건문을 줄이고자, 입력 배열을 0으로 감쌌다.
arr = [[0] * (M + 2)] + [[0] + list(map(int, input().split())) + [0] for _ in range(N)] + [[0] * (M + 2)]

memo = [[-1] * (M + 2) for _ in range(N + 2)]   # memo[i][j]에 대해 연산이 수행된 값이 0일 수 있기 때문에, 구분을 위해서 초깃값을 -1로 지정

def memoization(i, j):
    if i == 1 and j == 1:   # 베이스 조건: 출발지에서 출발지까지의 경로는 한개
        return 1
    if memo[i][j] != -1:    # 이미 계산된 memo값이 있을 경우, 해당 값을 반환
        return memo[i][j]
    else:
        memo[i][j] = 0                                          # 현재 위치에 대해 연산을 수행하므로 0으로 일단 수정
        for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):   # 상, 하, 좌, 우 4방향 탐색
            ni = i + di
            nj = j + dj
            if arr[i][j] < arr[ni][nj]:                         # 현재 위치가 주변 위치에 비해 낮을 경우,
                memo[i][j] += memoization(ni, nj)                   # 현재 위치까지의 경로 수 += 주변 위치까지의 경로 수
        return memo[i][j]                                       # 4방향에 대해 탐색이 이루어진 결과값 반환

print(memoization(N, M))