이번 문제는 깊이우선탐색과 다이나믹 프로그래밍을 이용해서 해결하였다. 처음에는 깊이우선탐색으로만 접근하였다. 단순하게 dfs() 함수에서 현재 위치보다 다음 위치가 작을 경우에 재귀호출 시키고 만약 [m-1][n-1]에 도달하면 전역변수를 1 증가시키는 방법으로 구현하였다. 테스트 케이스에 대한 정답은 잘 도출되었다.

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
def dfs(y, x):
    global cnt
    dy=[0, 0, -1, 1]
    dx=[1, -1, 0, 0]
    if y==m-1 and x==n-1:
        cnt+=1
        return
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if ny>=0 and nx>=0 and ny<m and nx<n and maps[ny][nx]<maps[y][x]:
            dfs(ny, nx)
m, n=map(int, input().split())
maps=[]
for _ in range(m):
    maps.append(list(map(int, input().split())))
cnt=0
dfs(0, 0)
print(cnt)

그러나 시간초과가 발생하였다. 질문하기를 찾아 본 결과 DFS + DP를 적용해야 시간 안에 해결할 수 있다는 사실을 알았다. 아마도 m과 n을 최댓값으로 넣었을 때에 수가 너무 커지기 때문인 것 같았다.

그래서 DFS + DP 방식으로 풀이하였다. dp리스트로 방문처리와 카운팅을 동시에 하였다. -1로 초기화를 시키고 dp[y][x]가 -1일 경우, 아직 방문하지 않은 위치로 판단하고 탐색을 진행하도록 하였고, -1이 아니라면 이전에 방문한 적이 있는 위치이므로 그 dp[y][x] 값을 더해주도록 하였다. 만약 [m-1][n-1]에 도달했다면 dp[y][x]에 1을 더해주었다.

DFS와 DP를 결합한 문제는 처음 접해보아서 많은 시간을 쏟았다. 조금은 찾아보면서 풀이하였다. 이런 문제들도 많이 풀어봐야겠다는 생각을 했다.

• dfs함수를 y, x를 인자로 갖도록 선언한다.
  -> 4가지 방향에 대한 정보를 dy, dx 리스트에 짝지어 저장한다.
  -> y가 m-1과 같고, x가 n-1과 같을 경우 1을 반환한다.
  -> dp[y][x]가 -1이 아닐 경우, dp[y][x]를 반환한다.
  -> dp[y][x]를 0으로 갱신한다. (방문처리)
  -> 4번 반복하는 i에 대한 for문을 돌린다.
  --> ny를 y+dy[i]로 저장한다.
  --> nx를 x+dx[i]로 저장한다.
  --> 만약 ny, nx가 0보다 크거나 같고, ny가 m보다 작고, nx가 n보다 작고, maps[ny][nx]가 maps[y][x]보다 작을 경우, dp[y][x]에 dfs(ny, nx)의 반환값을 더한다.
  -> dp[y][x]를 반환한다.
• m과 n을 입력받는다.
• 지도의 정보를 저장할 리스트 maps를 선언한다.
• m번 반복하는 for문을 돌린다.
  -> maps를 입력받는다.
• dp를 m*n의 -1로 채운다.
• dfs(0, 0)을 출력한다.

Code

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
def dfs(y, x):
    dy=[0, 0, -1, 1]
    dx=[1, -1, 0, 0]
    if y==m-1 and x==n-1:
        return 1
    if dp[y][x]!=-1:
        return dp[y][x]
    dp[y][x]=0
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if ny>=0 and nx>=0 and ny<m and nx<n and maps[ny][nx]<maps[y][x]:
            dp[y][x]+=dfs(ny, nx)
    return dp[y][x]
m, n=map(int, input().split())
maps=[]
for _ in range(m):
    maps.append(list(map(int, input().split())))
dp=[[-1]*n for _ in range(m)]
print(dfs(0, 0))