[백준] 1520 내리막길 - 파이썬

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

1520번: 내리막 길

 

---

문제 설명

0,0 에서부터 내려와 m, n까지 도착하는 경로의 개수를 찾는 것이 문제이다. 다음번 이동할 칸은 현재 칸의 값보다 작아야 이동할 수 있다. bfs를 돌면서 상하좌우를 체크해주면 되는데, 한번 방문한 좌표는 다시 방문할 수 있는 것이 특징이다.

한번 방문한 좌표는 다시 상하좌우를 체크해줄 필요가 없다. 그러므로 이전 경로까지 가는 경우의 수를 더해주기만 하면 된다.

이 문제에서의 중요한 점은, 칸을 내려갈 때 내림차순으로 진행해야 하는 것이다.

 

20(1, 3)좌표는 32 -> 20도 가능하고 32-> 30-> 25 -> 20도 가능하다. 즉 25에서 오는 경우 1개, 32에서 오는 경우 1개가 존재한다.그러므로 2가지 경로가 모두 계산되어야 하는데, 이 때 높이(순서)를 고려하지 않으면 25를 계산하는 경우보다 20을 계산하는 경우가 더 빨리 나오기 때문에 다음 좌표인 17로 가는 경로의 개수를 정확히 전달하지 못한다.

그러므로 우선순위 큐를 이용하여 탐색하고, 방문한 좌표인 경우에는 이전 좌표에 저장된 경로 값을 더해주면 된다.

 

큐를 출력해보면 다음과 같이 나온다는 것을 알 수 있다.

 

​코드

import sys, heapq

input = sys.stdin.readline

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

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

def search(x, y):
    q = []
    heapq.heappush(q, (-board[x][y], x, y))

    visited = [[0] * n for _ in range(m)]
    visited[x][y] = 1

    while q:
        now, x, y = heapq.heappop(q)
        now = now * -1 # heapq에 음수로 들어가 있음

        if x == m-1 and y == n-1:
            continue

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < m and 0 <= ny < n:
                if board[nx][ny] < board[x][y]:
                    if visited[nx][ny] == 0:
                        heapq.heappush(q, (-board[nx][ny], nx, ny))

                    visited[nx][ny] += visited[x][y]

    return visited[-1][-1]

print(search(0,0))