Python - 1520 - 내리막길

기존에 활동하던 블로그에서 옮겨온 포스팅 입니다.

내리막 길 click

 

 

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를 사용해서 시간복잡도를 향상시킬 수 있다.
그림을 보며 이해해보자.

 

 

 

 

먼저 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]까지 다시 가는 것이 아니라, 해당 칸에서 탐색을 마쳐도 된다. 이렇게 시간 복잡도를 줄일 수 있다.
• 마지막 세 번째 경로를 살펴보자. [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를 진행한다.
• 이후, 내리막으로 이동 가능한 칸에 대해 dfs()함수값을 받아와 모두 더해준다.

• dp의 값이 -1인 칸에 도착하면 해당 dp값을 우선 0으로 초기화 시켜 방문했다는 흔적을 남긴다.

• dp의 값이 -1이 아닌 칸에 도착하면 해당 dp값을 return한다. (방문했었다는 의미 임으로)

 

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
✔ - 2021.01.04