과정
*처음에 dfs로만 풀었는데, 이럴 경우 시간 초과가 발생 -> dp를 이용해야한다.
1.dfs(x,y)를 통해 낮은 곳으로만 이동 -> visited함수는 필요없음 why? 작은 곳으로만 이동하기 때문에 그 전 노드로는 가지 않게 됨
2. 2차원 dp설정 -> dp[x][y] = x,y에서부터 target까지의 경로 수
3. dfs에서 target에 도착하면 return 1
4. dp[x][y]!=-1이면 기존에 저장해둔 값을 리턴
import sys
input=sys.stdin.readline
n,m = map(int,input().split())
board=[]
for i in range(n):
board.append(list(map(int,input().split())))
dx=[1,0,-1,0]
dy=[0,1,0,-1]
answer=0
dp = [[-1 for i in range(m)] for j in range(n)]
def dfs(x,y):
if x==n-1 and y==m-1:
return 1
if dp[x][y]!=-1:
return dp[x][y]
dp[x][y]=0
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if nx>=0 and ny>=0 and nx<n and ny<m:
if board[nx][ny]<board[x][y]:
dp[x][y]+=dfs(nx,ny)
return dp[x][y]
if board[0][0]>board[n-1][m-1]:
answer = dfs(0,0)
print(answer)
time:30분
resolve:O 다시풀장 dp사용법을 참고해버림
