[백준] 내리막 길

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

1520번: 내리막 길

1. 문제 이해

제일 왼쪽 위 칸에서부터 제일 오른쪽 아래 칸으로 이동할 때 계속해서 높이가 낮아지도록 이동할 수 있는 내리막길로만 이동하는 경로의 개수를 구하는 문제입니다.

2. 문제 접근

첫번째 접근: DFS

단순하게 왼쪽 위 칸에서부터 오른쪽 아래 칸으로 이동을 DFS로 풀이하면 시간초과가 날 것이라고 생각했습니다. 그래서내리막 경로에 해당하는 칸들에 방문처리를 하고 만약에 탐색 도중 방문 처리된 칸을 만나면 경로의 수를 하나 늘려주는 방식으로 풀이하였습니다. 하지만 이 풀이는 미처 탐색하지 못하는 경로가 발생할 수 있어서 정해가 아닙니다.

4 4

16 9 8 1

15 10 7 2

14 11 6 3

13 12 5 4

 

두번째 접근: DP

예전에 비슷한 문제를 DP로 푼 기억이 있어서 DP로 접근해보았습니다. dp배열의 정의는 다음과 같습니다.

dp[i][j] = (i, j) 위치에 내리막길 경로로 도달 할 수 있는 경우의 수

가장 중요한 초기 조건은 제일 왼쪽 위인 dp[0][0]는 시작위치이므로 1이고 나머지 위치는 0에서 시작합니다. 그 다음 가장 높은 위치에서부터 4방향중 이동 가능한 위치에 현재 위치에 도달할 수 있는 경우의 수를 모두 더해주면 됩니다. 이것은  자신보다 높은 위치에 도달할 수 있는 경우는 모두 계산이 되어 있기 때문에 가능합니다.

3. 풀이

import sys
input = sys.stdin.readline

n, m = tuple(map(int, input().split()))

board = [
    list(map(int, input().split()))
    for _ in range(n)
]

order = [
    (y, x) for y in range(n) for x in range(m)
]

# 가장 높은 곳부터 내림차순으로 졍렬
order.sort(key= lambda x : board[x[0]][x[1]], reverse=True)

dp = [
    [0] * m
    for _ in range(n)
]

dp[0][0] = 1

dys = [0, 1, 0, -1]
dxs = [1, 0, -1, 0]

def inRange(y, x):
    return 0 <= x < m and 0 <= y < n


for y, x in order:
    for dy, dx in zip(dys, dxs):
        ny = y + dy
        nx = x + dx
        # 현재 자신보다 높은 곳은 계산이 되어있으므로 현재 높이에서 다음으로 이동할 수 있는 위치에
        # 현재 위치로 올 수 있는 경우의 수를 더해주면 된다.
        if inRange(ny, nx) and board[y][x] > board[ny][nx]:
            dp[ny][nx] += dp[y][x]


print(dp[n - 1][m - 1])

4.회고

DFS로 접근하니 별의별 접근을 다해보았던 것 같습니다. 3차원 배열을 통해서 현재 위치에 어느 방향을 보면서 도달할지부터 visited[a][b][c][d] (a, b) -> (c, d)로 온 경우까지 다 접근해보았는데 뚜렷하게 풀이가 보이지 않아서 DP로 접근해보았는데 쉽게 풀 수 있었습니다.

5. 배운점

가끔 정렬하다 TypeError를 만나는 경우가 있는데 높은 확률로 order.sort(key=lambda ...)에서 key를 빼먹은 경우였습니다.