[백준알고리즘] 1520번: 내리막 길 -Python

[백준알고리즘] 1520번: 내리막 길 -Python

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

1520번: 내리막 길

20200408

아래 새로 풀었다.

---

요즘 계속 DP를 다시 보고 있다. 오늘은 내리막 길을 풀어봤는데 금방 풀렸다.

개인적으로 dp 중에서는 쉬운 편이었다고 생각을 한다.

 

이번에는 최저의 방법을 구하는 것이 아닌 가능한 경우의 횟수를 구하는 문제다. 그러다 보니 풀고 난 후 다른 사람들의 코드를 보니 대부분이 거의 모두가 DFS를 이용해서 Bottom-up approach나 Top-down apporach를 이용해서 풀었다. 필자는 비슷하지만 조금 다르게 풀었기 때문에 DFS 방식으로 풀이를 한 것도 보는 것이 좋다고 생각한다.

 

이전 '평범한 배낭'문제 풀이에 쓴 내용에 DP에 대한 내용이다.

Memoization을 사용하며 과정 중에 sub problems을 풀어나가게 된다. 즉, Recursion이 기본적인 아이디어이다.

하지만, 구현시 무작정 재귀를 사용하는 것이 아닌 Overlapping sub problems를 Memoization 해두기 때문에 반복되는 일을 더 효과적으로 수행할 수 있다.

 

 

따라서 일단 입력받는 테이블 외에 path라는 하나의 테이블을 더 두었고, 추가한 테이블은 해당 지점 (i, j)까지 갈 수 있는 경로의 수를 나타내도록 했다. 하지만 DFS로 푼 다른 풀이와는 달리 단지 (0, 0)에서 출발해서 (i, j)까지 가는 경로가 아닌, 모든 경로에서 올 수 있다는 점이 다르다. 이때 결과적으로 (0, 0)의 높이보다 높은 곳에서 오는 경로는 0이 더해지니까 사실상 경로가 추가되지 않을 뿐이다.

 

 

기본적인 아이디어는 임의의 지점 (i, j)에서 상하좌우로 (i, j)보다 높은 위치인 지점이 있다면

'(i, j)까지 올 수 있는 경우 += 높은 지점까지 올 수 있는 경우' 인 것이다.

따라서 상하좌우에 높은 곳이 여러개라면 (i, j)의 경로의 수는 그만큼 증가하게 되는 것이다.

처음 path테이블은 -1로 모두 초기화 시킨 후 경로가 없으면 0, 경로가 있으면 그 경로의 값만큼 가지게 되게 된다. 출발지점보다 높은 곳과 상하좌우가 모두 자신보다 낮은 높이의 지점이라면 경로의 수가 0이기 때문에 해당하는 지점들의 인접한 곳들은 0을 더하기 때문에 상관이 없게 되는 아이디어이다.

 

 

이해를 돕기 위해 간단히 몇가지의 예를 들어보면 다음과 같다.

5  4  3

3  5  1

2  1  0

와 같은 높이의 길이 있다고 했을 때, 경로의 수를 본다면,

1  0  0

0  0  0

0  0  0

으로 시작을 한다.

 

(0, 1)의 위치에서 보면

5  4  3

   5

의 형태로 둘러쌓여있게 되는데, 4보다 큰 왼쪽과 아래에서 4로 갈 수 있기 때문에 각각 "왼쪽지점에 도착할 수 있는 경로의 수 + 아래지점에 도착할 수 있는 경로의 수 = 자신(4)에 도착할 수 있는 경로의 수" 인것이다.

여기서 왼쪽지점 5에 도착할 수 있는 경로의 수는 1이고, 아래지점 5에 도착할 수 잇는 경로의 수는 0이기 때문에 4로 갈 수 있는 경로의 수는 1이 된다.

 

마찬가지로 진행을 하게 되면

1  1  1

1  0  1

1  1  

까지 경로의 수가 채워지게 된다.

 

마지막에서는 0으로 갈 수 있는 방법이 위쪽의 1에서와 왼쪽에서의 1에서 갈 수 있다. 그렇기 때문에 0 + 1 + 1 = 2가 되어 최종적으로 아래와 같은 경로의 수 테이블이 완성이 되고 최종 경로의 수는 2가 된다.

1  1  1

1  0  1

1  1  2

 

 

말로 설명을 하다보니 횡설수설하며 이해하기 힘들 것 같지만 코드만 봐도 금방 이해할 수 있을 것 같아 코드만 첨부하겠다.

import sys


def dp(i: int, j: int):
    global table, path, M, N
    if path[i][j] > 0:
        return

    path[i][j] = 0
    # up
    if i > 0 and table[i - 1][j] > table[i][j]:
        if path[i - 1][j] < 0:
            dp(i - 1, j)
        path[i][j] += path[i - 1][j]

    # down
    if i < M - 1 and table[i + 1][j] > table[i][j]:
        if path[i + 1][j] < 0:
            dp(i + 1, j)
        path[i][j] += path[i + 1][j]

    # left
    if j > 0 and table[i][j - 1] > table[i][j]:
        if path[i][j - 1] < 0:
            dp(i, j - 1)
        path[i][j] += path[i][j - 1]

    # right
    if j < N - 1 and table[i][j + 1] > table[i][j]:
        if path[i][j + 1] < 0:
            dp(i, j + 1)
        path[i][j] += path[i][j + 1]


(M, N) = map(int, sys.stdin.readline().split())
table = []
path = []

for i in range(M):
    table.append(list(map(int, sys.stdin.readline().split())))
    path.append([-1] * N)
path[0][0] = 1

for i in range(M):
    for j in range(N):
        dp(i, j)
        
print(path[-1][-1])

 

20200408

새롭게 풀 때 더 어렵게 풀었었다.. 머리가 터지는 줄 알았다.. 위에 보니 쉬웠다고 써놨던데..

이번에는 재귀방식을 사용하면서 (0, 0)에서 출발을 해서 탐색을 했지만 도착지점부터 차례대로 올라오면서 경로의 수를 합쳤다. 

 

상하좌우에 현재 자신의 위치보다 낮은 지점이 있을 경우 해당 지점들이 갖는 경로의 수의 합을 현재 위치에 합하도록 했다. 한 번 방문해서 경로의 수를 갖고있다면 그대로 반환하고, 방문한 적이 없던 지점이라면 새롭게 경로의 수를 구하게 된다.

#20200425 새로풀었는데 너무 비슷하게 풀어서 덮어씀

from sys import setrecursionlimit
setrecursionlimit(10**9)

def dfs(x, y):
    if x == n-1 and y == m-1: return 1
    rtn = 0
    for d in range(4):
        i, j = x + dx[d], y + dy[d]
        if 0 <= i < n and 0 <= j < m and mountain[i][j] < mountain[x][y]:
            if visited[i][j] >= 0:
                rtn += visited[i][j]
            else:
                rtn += dfs(i, j)
    visited[x][y] = rtn
    return rtn

n, m = map(int, input().split())
mountain = [list(map(int, input().split())) for _ in range(n)]
visited = [[-1] * m for _ in range(n)]
visited[0][0] = 0
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
print(dfs(0, 0))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다