[백준/BOJ] #1520 내리막 길.python(파이썬)

문제 링크 / 출처

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

1520번: 내리막 길

 

문제 요약

시작점(좌상단)에서 도착점(우하단)까지 갈 수 있는 경로의 경우의 수를 구하는 문제

현재 위치보다 더 낮은 숫자(높이)인 칸(지점)으로만 이동가능

[제약사항]

• 1 <= N, M <= 500
• 1 <= 각 지점의 높이 <= 10000

 

풀이

- 최대힙을 이용해 풀이했다.

 

- 시작점에서 출발하여 이동가능한 지점(높이가 더 낮은 지점)의 높이와 위치를 힙에 저장한다.

 

- 높이가 높은 점부터 방문하도록 최대힙으로 구현하여 특정지점에 도착할 수 있는 모든 경우의 수를 파악한 뒤 다음 지점으로 이동할 수 있도록 했다.

 

- 백준에서 살펴본 다른사람들의 풀이들이 거의 모두 재귀를 이용한 dfs + dp인 것을 보면 내 풀이는 정석은 아닌듯 하다..

 

코드

from heapq import heapify, heappop, heappush
import sys

input = sys.stdin.readline

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

drc = [(1, 0), (0, 1), (-1, 0), (0, -1)]
arr = [[0] * M for _ in range(N)]
arr[0][0] = 1

# 최대힙으로 사용하기 위해 높이를 음수로 저장
que = [(-board[0][0], 0, 0)]

while que:
    height, r, c = heappop(que)
    for dr, dc in drc:
        nr, nc = r + dr, c + dc
        # 갈수 있는 지점인지 확인
        if not (0 <= nr < N and 0 <= nc < M) or board[nr][nc] >= board[r][c]:
            continue

        # 이미 방문한 지점인지 확인
        # 방문한 적 없는 지점만 다음에 이동할 지점으로 추가해줌 
        if not arr[nr][nc]:
            heappush(que, (-board[nr][nc], nr, nc))

        # 경우의 수 추가
        arr[nr][nc] += arr[r][c]

print(arr[-1][-1])