[dp/백준] 1520번: 내리막길

-문제:https://www.acmicpc.net/problem/1520

dfs랑 dp를 이용해서 풀어야하는 문제다. dfs는 어찌저찌 구현했는데, 경로가 겹칠 때 가짓수를 추가하는걸 어떻게 해야할지 몰랐다. 경로 갯수를 어떻게 누적해야하는지 몰랐던 문제. 골드 4레벨 문제였다. 

 

-정답풀이: 

재귀함수로 진행되므로 탈출 조건을 명시한다(x==m-1 and y=n-1)

dp[x][y]!=-1인 경우는 (x,y)를 지나간 경로가 있다는 말이므로, 그때의 값을 반환한다 

그게 아닌 경우는 (x,y)는 처음 지나가는 것이므로 dp[x][y]=-1+1=0을 해준다 

 

내리막길이므로, data 값이 작은 경우에만 dfs를 실행한다. 

다음 이동 지점에 대한 dfs값을 (x,y) 경로 경우의 수의 값에 추가한다 

m,n=map(int,input().split())
data=[]
for _ in range(m):
    data.append(list(map(int,input().split())))
dp=[[-1]*n for _ in range(m)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]

def dfs(x,y):
    if x==m-1 and y==n-1:
        return 1   
    if dp[x][y]!=-1:
        return dp[x][y]
    dp[x][y]=0    
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<m and 0<=ny<n:
            if data[nx][ny]<data[x][y]:
                dp[x][y]+=dfs(nx,ny)
    return dp[x][y]
print(dfs(0,0))