악곱 == 악성곱슬

DP, DFS

---

이 문제는 왼쪽 상단에서 오른쪽 하단까지 가는 경로의 개수를 구하는 문제이다. 단 경로의 조건은 현재 위치보다 숫자가 작은 인접 칸으로만 이동할 수 있다는 것이다.

그래서 이 문제의 조건은 위 내용 단 하나이고 시작, 끝 위치가 정해져있다는 점이다.

따라서 문제를 어떤 방식으로 풀어야 하는가를 고민해봤을때는, DFS, 즉 경로를 끝가지 가서 오른쪽 하단이 나오는지부터 탐색을 해봐야 한다.

• DFS를 (0, 0) 좌표를 시작점으로 두고 시작

DFS

1. 만약 현재 좌표가 우측 하단에 도착했다면 1을 반환 (경로가 있다는 뜻)
2. 아니라면 상,하,좌,우 를 탐색
   1. 인덱스 범위 밖이라면 pass
   2. 내리막길이 아니라면 pass
   3. 다음 좌표로 다시 DFS 시작 → 2로 돌아감
3. 하위 sub problem에서 나온 반환 값(경로의 개수) 의 합을 반환. = 현재 내 problem의 경로 최댓값

이렇게 코드를 짜면 정말 많은 중복 문제들이 발생한다. 따라서 DFS, 재귀 방식으로 문제를 구현할 때 부분 중복 문제를 제거할 수 있는 메모이제이션(memoization)을 사용해서 시간 복잡도를 줄인다.

이를 모두 적용한 코드는 다음과 같다.

구현

---

import sys

def dfs(x, y, des_x, des_y):
    if x == des_x and y == des_y:
        mem[x][y] = 1
        return mem[x][y]
    answer = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 인덱스 범위 밖
        if nx < 0 or ny < 0 or nx > des_x or ny > des_y:
            continue
        # 내리막길이 아니면
        if graph[nx][ny] >= graph[x][y]:
            continue
        # 메모이제이션 된 값이 없다면
        if mem[nx][ny] == -1:
            mem[nx][ny] = dfs(nx, ny, des_x, des_y)
        answer += mem[nx][ny]
    return answer

if __name__ == "__main__":
    sys.setrecursionlimit(100000)
    M, N = map(int, sys.stdin.readline().rstrip().split())
    graph = []
    mem = [[-1]*N for _ in range(M)]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    for _ in range(M):
        graph.append(list(map(int, sys.stdin.readline().rstrip().split())))
    print(dfs(0, 0, M-1, N-1))