[BOJ] 1520번 내리막 길

 

[BOJ] 1520번 내리막 길

---

처음에는 DP와 BFS로 푸는 문제로 접근하였다.

생각하였던 예시 중에서는 올바르게 동작하였으나, 제출 시 시간 초과가 걸려 실패하였다.

왜 그런지 곰곰히 생각해보던 도중 BFS로 구현을 하게 되면 순차적으로 탐색을 하게 되어 돌아서 가는 경우에 대해서 갱신하여 처리하기 어렵다.

따라서 어차피 숫자 가중치에 따라 더 큰것부터 우선으로 찾아 들어가야하기 때문에 BFS의 Queue를 우선순위 Queue로 구현해볼까라고 생각하였다.

 

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

1520번: 내리막 길

 

알고리즘

---

1. BFS로 탐색 구현

2. 탐색 시 우선 순위 Queue에 남아있는 값중 제일 큰 값부터 순차적으로 적용

3. 해당되는 값을 각 영역별로 갯수 저장(주의점 이미 반영되었다면 , 우선 순위 Queue에는 다시 넣으면 안된다)

4. 탐색이 종료되면, 마지막 영역에 대해 값 출력

 

코드

---

#BOJ 1520번

import heapq

dx , dy = [0,0,-1,1] , [1,-1,0,0]
n , m = map(int,input().split())

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

heapq.heappush( q , (-maps[0][0] ,0,0) )

while q :
    current,x,y= heapq.heappop(q)
    current = -1*current
    for i in range(4):
        nx , ny = x+dx[i] , y+dy[i]
        if 0<=nx<n and 0<=ny<m and maps[nx][ny] < current :
            if dp[nx][ny]==0 :
                heapq.heappush( q , (-maps[nx][ny],nx,ny))
            dp[nx][ny] += dp[x][y]

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