[백준/Python] 1520 내리막길

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

문제 분석

난이도

골드 3

분류

그래프 탐색, 다이나믹 프로그래밍 + (DFS or 우선순위 큐)

문제

문제 풀이

풀이

맨 마지막 위치에서 인접한 부분의 자신보다 큰 수를 우선순위 큐에 넣어준다. 그러면 항상 앞에는 작은 수가 들어가고 그 순서대로 탐색하게 된다.

주변의 인접한 숫자들 중 자신보다 큰 수가 있다면 현재의 방문횟수를 더해주고, 방문한 적이 없는 곳이라면 우선순위 큐에 넣어준다.

M*N은 최대 250000(500*500) 이고, push pop의 시간복잡도는 logN이므로 시간은 넉넉하다.

 

소스코드

from sys import stdin
from heapq import heappop,heappush
input=stdin.readline

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

n,m=map(int,input().split())
arr=[list(map(int,input().split())) for i in range(n)]
vi=[[-1]*m for i in range(n)]

vi[-1][-1]=1
hq=[(arr[-1][-1],m-1,n-1)]

while hq:
    v,x,y=heappop(hq)
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if -1<nx<m and -1<ny<n:
            if vi[ny][nx]==-1:
                vi[ny][nx]=0
                heappush(hq,(arr[ny][nx],nx,ny))
            if arr[ny][nx]>v:
                vi[ny][nx]+=vi[y][x]

print(vi[0][0])

후기

 

DFS+DP로도 풀릴 문제지만 위 방법이 더 쉽지 않을까 생각한다.