[BOJ] 1520. 내리막 길 (🥇, DP)

🔗

풀이

항상 (0, 0)에서 시작해서 (M-1, N-1)로 이동하게 된다. 이동할 때 도중에 뛰어넘거나 할 수 없기 때문에 반드시 모든 길은 연결되어 있다. A에서 A와 인접한 곳으로 갈 수 있는 경우의 수는 일단 A까지 가는데 걸리는 경우의 수에 추가적으로 더해지는 것이다. 특정 위치에 도달할 수 있는 경우의 수를 계속 누적해서 구하는 것, 다이나믹 프로그래밍으로 해결할 수 있다

2차원 배열에서 dp를 구현할 땐 어떤 방향으로 진행할 것이냐가 문제가 되는데, 이 문제에서는 반드시 작은 숫자가 있는 방향으로만 이동할 수 있다는 힌트가 있다. 항상 왼쪽 위에서 시작하게 되고, 어떤 값을 지나가도 그 값보다 더 큰 값으로는 이동할 수 없다. 이동할 때마다 반드시 더 작은 값으로 이동해야 한다. 상하좌우로 모두 이동할 수 있기 때문에 더 작은 행에서 더 큰 행으로 이동하거나 하는 위치 방식으로는 어렵다. 만약 그렇게 되면 위쪽 칸에 더 작은 값이 있었던 경우는 제대로 된 dp가 이루어지기 어렵다. dp는 이전에 구한 값이 확실하다고 가정하고 그 값을 갖고 다음 값으로 넘어가게 되기 때문이다.

하지만 무조건 작은 값으로만 이동해야 한다는 조건이 붙는다면, 항상 모든 이동은 더 큰 값에서 더 작은 값으로 이루어지게 되고, 계속해서 더 큰 값을 가지는 칸들에 우선순위를 주면서 이동을 시키면 각 칸에 대한 경우의 수를 제대로 구할 수 있다. 더 큰 숫자를 가지는 칸부터 찾게 되면 이미 방문했던 칸을 재방문하진 않을 것이기 때문이다.(항상 더 작은 값으로만 가니까)

배열의 크기는 500x500으로 총 25만칸이고 매번 최대값을 찾는 방식을 수행하게 되면 시간이 꽤 오래 걸릴 것 같아서 최대힙을 사용한 우선순위큐를 써서 구현했다.

# 내리막 길

from heapq import heappop, heappush

m, n = map(int, input().split())
MAP = [list(map(int, input().split())) for _ in range(m)]
dp = [[0]*n for _ in range(m)]
start = MAP[0][0]

dp[0][0] = 1
pq = [(-start, 0, 0)]
dx, dy = (-1, 0, 1, 0), (0, 1, 0, -1)
while pq:
    num, x, y = heappop(pq)
    if MAP[x][y] == start+1:
        continue

    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if not(-1<nx<m and -1<ny<n) or MAP[nx][ny] >= -num:
            continue
        dp[nx][ny] += dp[x][y]
        heappush(pq, ((-MAP[nx][ny], nx, ny)))
    MAP[x][y] = start+1

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