[Python]동적계획법2 백준 1520

   문제

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

처음 코드를 짤때 너무 간단하게 생각했다.

내리막길로만 갈 수 있다는걸 아래쪽으로만 이동할수 있는걸로 코드를 작성했고 당연히

 실패했다.위로 올라갔다가 내려올수도 있다는걸 생각하지못했다.

import sys
 
N,M=map(int,sys.stdin.readline().split())
 
map=[list(map(int,sys.stdin.readline().split())) for _ in range(N)]
 
 
 
 
result=[[0 for _ in range(M)] for _ in range(N)]
result[0][0]=1
 
 
 
for i in range(N):
    if i==0:
        for j in range(1,M):#첫줄 처리 오른쪽으로만 확인하고 중간에 끊어지면 끝
            if map[i][j-1]>map[i][j]:
                result[i][j]+=result[i][j-1]
            else:
                break
 
    else:
        for d in range(M):#아래로 이동하면서 비교
            if map[i][d]<map[i-1][d]:
                result[i][d]+=result[i-1][d]
        for r in range(1,M):#우로 이동하면서 비교
            if map[i][r - 1] > map[i][r]:
                result[i][r] += result[i][r - 1]
        for l in range(M-1,0,-1):#좌로 이동하면서 비교
            if map[i][l]>map[i][l-1]:
                result[i][l-1]+=result[i][l]
 
print(result[-1][-1])

위만 추가해주면 될거같지만 그렇게 간단하지는 않았다.

만약 해당 지점으로 올수있는 가능성이 있는곳(상하좌우 중 해당 지점보다 높은지역)이

 한번도 방문하지 않았다면 먼저 한번도 방문하지 않았던 곳으로 올수있는 경로를 역으

로 찾아준뒤 더해주어야한다. 

4 4

10 9 6 5

1 8 7 4

10 1 2 3

10 4 3 2

이 문제를 예시로 들어보면

탐색순서는 위와 같이 해주고 방문하지 않은 곳을 -1로 초기화 시켜준뒤 시작해보자

[1, -1, -1, -1]

[-1, -1, -1, -1]

[-1, -1, -1, -1]

[-1, -1, -1, -1]

0,1을 봤을때

좌측에서 올수있고 아래와 우측에서는 올수없다.

[1, 1, -1, -1]

[-1, -1, -1, -1]

[-1, -1, -1, -1]

[-1, -1, -1, -1]

이런식으로 표현할수있다.

0,2를 봣을때

좌측과 아래에서 올수있다.

좌측은 방문했던적이 있기때문에 그대로 더해주고

아래측이 문제이다. 한번도 방문한적이 없기때문에 추적해 주어야한다.

[1, 1, 1, -1]

[-1, 1, 0, -1]

[-1, -1, -1, -1]

[-1, -1, -1, -1]

아래에서 올수있는 경로를 모두 탐색해주어야 한다.

이부분을 재귀로 반복하여 방문하였던곳 나오거나 탐색할수 없을때까지 찾아준다

[1, 1, 2, -1]

[-1, 1, 1, -1]

[-1, -1, -1, -1]

[-1, -1, -1, -1]

0,2가 마무리되면 이런모습을 보여줄수 있을것이다.

[1, 1, 2, 2]

[-1, 1, 1, -1]

[-1, -1, -1, -1]

[-1, -1, -1, -1]

0,3이 마무리 되면 이런모습이다.

이렇게 하면 아래에서 위로 올라가는 것도 반영할수있다.

코드로 살펴보자

방향성이 한방항으로 정해져있기때문에 사이클의 걱정은 하지않아도 된다.

 
import sys
 
 
def dp(i,j,N,M):
    if path[i][j]>0:#한번이라도 방문햇다면
        return
    path[i][j]=0#방문표시를 해준다.
    #네방향에서 올 수 있는 길을 모두 더해준다.
    #아래쪽에서 위로 오는경우
    if i>0 and map[i-1][j]>map[i][j]:#아래쪽이 더클때
        if path[i-1][j]<0:#아래쪽이 한번도 방문하지 않은상태라면
            dp(i-1,j,N,M)#방문할수 있는곳들을 재귀를 이용하여 모두찾는다.
        path[i][j]+=path[i-1][j]#path[i-1][j]로 올수 있는곳 길을 모두 찾았다면 더해준다.
    #위에서 아래로
    if i<N-1 and map[i+1][j]>map[i][j]:
        if path[i+1][j]<0:
            dp(i+1,j,N,M)
        path[i][j]+=path[i+1][j]
    #왼쪽에서 오른쪽으로
    if j>0 and map[i][j-1]>map[i][j]:
        if path[i][j-1]<0:
            dp(i,j-1,N,M)
        path[i][j]+=path[i][j-1]
    #오른쪽에서 왼쪽으로
    if j<M-1 and map[i][j+1]>map[i][j]:
        if path[i][j+1]<0:
            dp(i,j+1,N,M)
        path[i][j]+=path[i][j+1]
 
 
 
 
N,M=map(int,sys.stdin.readline().split())
 
map=[list(map(int,sys.stdin.readline().split())) for _ in range(N)]
 
path=[[-1 for _ in range(M)] for _ in range(N)]
path[0][0]=1
 
for i in range(N):#행
    for j in range(M):#열
        dp(i,j,N,M)
 
print(path[-1][-1])