내리막 길

2020.10.13 오늘 내내 이 문제를 잡고 씨름했다.⚡

먼저 두 시간 동안은 접근을 잘못해 고생했다. 어설프게 dp 점화식을 찾았다. 입력 받은 리스트의 첫 줄 부터 차근차근 값을 쌓아나가는 방식이었다. 만약에 직사각형의 아래 칸으로만 이동할 수 있고, 윗 행으로는 이동하지 못한다면 맞는 풀이었지만, 문제에서는 그런 조건이 없었기에 당연히 틀렸다.

반례

4 4
16 9 8 1
15 10 7 2
14 11 6 3
13 12 5 4

이 반례처럼 ‘ㄹ’자로 내려갔다 올라갔다를 반복할 수도 있는 것이다.

결국 검색을 통해 풀이 방법을 찾아보았다… DFS를 통해 길을 탐색하고, 여기에 DP를 이용해 시간을 단축시켜 푸는 문제였다.

예제 입력 1을 통해 알아보자.

4 5
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10

문제에 설명되어 있듯이 이 지도에서는 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수가 3개다. DFS 깊이탐색을 이용해 [1,1]부터 [m,n]까지 해당 칸의 숫자보다 작은 칸으로만 이동하면 3가지 임을 쉽게 찾을 수 있다.

이렇게만 풀면 입력 숫자의 크기가 비교적 크기 때문에 바로 시간초과가 발생한다. 여기에 추가로, DP를 사용해서 시간복잡도를 향상시킬 수 있다. 그림을 보며 이해해보자.

Crepe

먼저 dp를 모두 -1로 세팅해준다. 0으로 하지 않는 이유는 방문을 했는지 여부를 알기 위해서이다. 그리고 목표지점 [m,n]의 값은 1을 넣어준다. 목표지점에 도착하면 탐색을 종료해야 하기 때문이다.(혹시, 이해가 안된다면 그렇구나 하고 넘어갔다가 글을 다 읽고 다시 읽어보자. 그땐 이해가 될 것이다.)

DFS를 사용해 최초로 [m,n]에 도달했을 때, [1,1]부터 [m,n]까지 가는 경로의 수가 탐색이 덜 끝났기 때문에 아직 1가지 이다. 따라서, 해당 탐색을 거쳤던 경로의 DP값을 모두 1로 바꾸어 준다.

[1,4]에서 첫 번째 경우에는 아래로 갔다면, 이번에는 오른쪽으로 탐색해 나간다. 이 경로를 거치다 보면 [2,4]에서 이미 탐색이 끝난 ‘1’이 저장되어 있는 값을 만난다.

[2,4]로 부터 [m,n]까지 깊이 탐색을 끝마쳤다는 뜻임으로 [2,4]에서 [m,n]까지 가는 경로의 수가 1가지 라는 뜻이다. 따라서, [2,4]를 지나쳐 [m,n]까지 다시 가는 것이 아니라, 해당 칸에서 탐색을 마쳐도 된다. 이렇게 시간 복잡도를 줄일 수 있는 것이다. 탐색을 마친 지점의 값이 1 이었음으로 경로의 값들에 모두 1을 더해준다.(여기서 -1은 탐색을 하지 않았다는 의미로, 실제로는 0이라는 값을 가지고 있다고 생각할 수 있음으로 0에 +1을 해 1이 된다.)

마지막 세 번째 경로를 살펴보자. [0,0]에서 아래로 탐색해 나가다 보면 [4,4]에서 -1이 아닌 값(방문했던 칸)을 만나게 된다. 이 칸에서 목표지점까지 갈 수 있는 방법은 저장되어 있는 값(= 1가지)임으로 경로에 있던 수들에 모두 1을 더해준다.

결과적으로, [0,0]으로 부터 [m,n]까지 갈 수 있는 경로의 수는 3가지가 된다.


코드로 구현하기 위해서는 값을 저장할 dp리스트와 dfs함수를 사용한다.

dp[][]

  • 초기에 목표 지점을 제외한 모든 값을 -1로 세팅한다.(목표지점에서 목표지점으로 갈 수 있는 방법은 1가지 임으로 dp[-1][-1]=1)
  • dfs를 진행하며 dp의 값이 -1이 아닌 칸(방문했던 칸)에 도달하면 해당 값을 경로에 속해있는 칸에 모두 더해준다.
  • 각 칸에 저장되어 있는 값은 해당 칸으로 부터 목적지 까지 갈 수 있는 경로의 수를 나타낸다.

dfs()

  • dp의 값이 -1 이며, 해당 칸 보다 작은 값을 가진 칸을 향해 DFS를 진행한다.
  • dp의 값이 -1이 아닌 칸에 도착하면 해당 dp값을 return한다.
  • dp의 값이 -1인 칸에 도착하면 해당 dp값을 우선 0으로 초기화 시켜 방문했다는 흔적을 남긴다.
  • 이후, 내리막으로 이동 가능한 칸에 대해 dfs()함수값을 받아와 모두 더해준다.


CODE

import sys
read=sys.stdin.readline
sys.setrecursionlimit(1000000000)

m,n=map(int,read().split())
road=list(list(map(int,read().split())) for _ in range(m))

dp=list(list(-1 for _ in range(n)) for _ in range(m))
dp[-1][-1]=1

dx=[0,-1,0,1]
dy=[1,0,-1,0]

def dfs(i,j):
    if dp[i][j] != -1:
        return dp[i][j]
    dp[i][j]=0
    for x,y in zip(dx,dy):
        if 0<=i+x<m and 0<=j+y<n and road[i+x][j+y]<road[i][j]:
            dp[i][j]+=dfs(i+x,j+y)
    return dp[i][j]
print(dfs(0,0))

고민했던 시간과 난이도에 비해 코드가 너무 간단해 보여서 허무한 감이 있다. 꼭 다시 풀어보자!🌈


[다시 풀어보기] ✔ - 2020.10.24