[백준] 1520번 : 내리막길

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

1520번: 내리막 길

해당 문제는 깊이 우선탐색으로 자기자신보다 값이 낮을 경우 이동하면 된다.

0,0 의 위치에서 N,M의 위치까지 탐색을 하면 되는데 상,하,좌,우로 갈 수 있고 상,하,좌,우 중에서 자기자신보다 값이 낮으면 해당 위치를 깊이 우선 탐색을 하면 된다. 그러나 예제의 문제 2번째와 3번째는 20 의 위치를 지날때 중복되는 것을 알 수 있다.

3번째 탐색을 할때에 20을 위치를 지날때 이미 2번째에서 이미 도달했기때문에 더이상 탐색을 할 필요가 없다.

 

따라서 이미 도달한 위치는 탐색을 할필요없이 경로만 추가해주면 된다.

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]  # 상하좌우 이동

M, N = map(int, input().split())
table = [list(map(int, input().split())) for _ in range(M)]

dp = [[-1] * N for _ in range(M)]  # 동적 계획법을 위한 메모이제이션 배열

def dfs(i, j): # 깊이우선탐색
    if i == M-1 and j == N-1:  # 목표 지점에 도달하면 1을 반환
        return 1

    if dp[i][j] != -1:  # 이미 계산한 값이 있으면 그 값을 반환
        return dp[i][j]

    dp[i][j] = 0  # 현재 위치에서 가능한 경로의 수를 저장할 변수

    for dx, dy in move:
        nx, ny = i + dx, j + dy

        if 0 <= nx < M and 0 <= ny < N and table[nx][ny] < table[i][j]:
            dp[i][j] += dfs(nx, ny)  # 내리막길로 이동할 수 있는 경우 경로의 수 누적

    return dp[i][j]

result = dfs(0, 0)
print(result)