[백준 1520번] 내리막(파이썬)

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

1520번: 내리막 길

상당히 까다로웠던 dp문제.

DP+길찾기가 합쳐져서 어려웠습니다.

 

   
#백준 1520번 내리막길
#시간초과 코드
from collections import deque
dx=[0,0,1,-1]
dy=[1,-1,0,0]
N,M=map(int,input().split())

room=[list(map(int,input().split())) for _ in range(N)]
dp=[[0]*M for _ in range(N)]
dp[0][0]=1

q=deque()
q.append((0,0))

while q:
    x,y=q.popleft()
    now=room[x][y]
    for d in range(4):
        nx=x+dx[d]
        ny=y+dy[d]

        if nx<0 or nx>=N or ny<0 or ny>=M:
            continue

        if room[nx][ny]<now:
            dp[nx][ny]+=1
            q.append((nx,ny))

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

처음에 제출한 방식입니다.

길을 돌면서 현재 방문한 지역의 dp에

1을 더해주는 방식이었습니다.

이 방식은 시긴초과를 유도합니다.

왜냐하면 같은 지점을 또 방문하기 때문인데요.

위의 예제에서 경우를 살펴보면

그림에서 20으로 가는 경로는 총 2개입니다.

실제로 20 이후로 내려가는 경로가 1개이지만

32에서 갈라지는 길은 총 2개이므로

프로그램이 2번 경로를 움직여야합니다.

이게 2개니깐 그나마 별거 안되는것처럼 보이지,

만약에 겹쳐지는 데까지 경로가

총 100개 되고

겹친 후에 경로가 또 100여개가 된다하면

100*100-->10000개의 탐색을 진행해야합니다.

이렇게 되면 시간초과가 발생할 수 밖에 없죠.

 

결국 dp를 어떻게 쓰느냐의 문제인데...

머리로 도저히 답이 안나와서 질문게시판의 힌트를 참고해서

우선순위 큐를 활용했습니다.

우선순위대로 받아주고 탐색하는 경우.

처음에는 가능한 경로에 있는

dp값이 업로드됩니다.

그리고 높이가 큰 순서대로 돌다가

만약 겹치는 곳으로 오게 되면

이미 방문처리한 곳이니

dp값만 계산해서 넘겨주고

더 방문할 필요는 없습니다.

그래서 만약 아래처럼

100개의 경로가 겹치고

이후에 100개의 경로가 갈라질 때

100+100=200

이렇게 탐색할 수 있어서 시간을 확 줄여줍니다.

#백준 1520번 내리막길
from heapq import heappop,heappush
dx=[0,0,1,-1]
dy=[1,-1,0,0]
N,M=map(int,input().split())

room=[list(map(int,input().split())) for _ in range(N)]
dp=[[-1]*M for _ in range(N)]
dp[0][0]=1

q=[]
heappush(q,[-room[0][0],0,0])

while q:
    tmp,x,y=heappop(q)
    now=tmp*(-1)
    if x==N-1 and y==M-1:
        continue

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

        if nx<0 or nx>=N or ny<0 or ny>=M:
            continue

        if now>room[nx][ny]:
            if dp[nx][ny]==-1:
                dp[nx][ny]=dp[x][y]
                go=room[nx][ny]*(-1)
                heappush(q,[go,nx,ny])
            else:
                dp[nx][ny]+=dp[x][y]
                continue
if dp[N-1][M-1]==-1:
    print(0)
else:
    print(dp[N-1][M-1])

dp에 대해서는 언제나 어려운데

이 문제로 dp를 왜 써야되는지에 대한 이해를 많이 가져갔습니다.

dp문제로 점검해보기 좋은 문제입니다.