[BOJ 1520] 내리막 길(Python)

문제

내리막 길

---

문제 해설

이 문제는 DP 혹은 DFS를 이용하여 풀 수 있습니다. 주의할 점은 이 문제가 가장 빠르게 내려가는 것을 요구하는 것이 아닌, 내려갈 수만 있는 경로라면 모두 채택한다는 점입니다.

가장 빠르게 내려만 간다면 오히려 쉽게 구현할 수 있습니다. 사방탐색이 아닌 오른쪽, 밑만 보면 되기 때문입니다.

하지만 그게 아니기 때문에 4방탐색으로 풀어야 하고 DFS를 활용하거나 DP를 이용해야합니다.

DFS로 푸는 방법은 (0, 0) 에서 시작하여 끝 지점에 도달할 시 카운트해주면 됩니다. 어차피 자기 자신보다 낮은 지점으로만 이동하기 때문에 방문 체크 배열도 필요 없습니다. 모든 경우의 수를 요구하기에 가능한 방법입니다.

DP로 푸는 방법은 다음과 같습니다.

1. 각 지점으로 가는 경우의 수를 메모이제이션해줄 2차원 리스트를 만들고 (0, 0) = 1, 나머지 지점은 0으로 초기화 합니다.
2. 높은 지점부터 4방향을 확인한 뒤, 자신보다 낮은 지점에 현 지점의 경우의 수를 더해줍니다.
3. 마지막 리스트를 확인합니다.

가장 중요한 것은 높은 지점부터 시작하여 끝까지 진행하는 것인데, 정렬을 이용해도 되고 우선순위 큐를 이용해도 됩니다.
저는 우선순위 큐를 이용해서 (최대 힙) 구현해 보았습니다.

---

풀이 코드

import sys
import heapq

input = sys.stdin.readline
n, m = map(int, input().split())
pq = []  # 최대 힙
dp = [[0] * m for _ in range(n)]
dp[0][0] = 1
graph = [list(map(int, input().split())) for _ in range(n)]

for i in range(n):
    for j in range(m):
        heapq.heappush(pq, (-graph[i][j], i, j))

# 최대힙에서 하나씩 빼면서 더해준다.
dx = -1, 0, 1, 0
dy = 0, 1, 0, -1
while pq:
    h, x, y = heapq.heappop(pq)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 범위 안이면서 자신보다 작은 수일 경우
        if 0 <= nx < n and 0 <= ny < m and graph[x][y] > graph[nx][ny]:
            dp[nx][ny] += dp[x][y]
print(dp[n - 1][m - 1])

---