DFS + 메모이제이션 (Memoization)

DFS + 메모이제이션 (Memoization)

1. 개념

DFS(깊이 우선 탐색)는 모든 경우의 수를 탐색하는 알고리즘이지만, 동일한 상태를 여러 번 탐색하면 비효율적입니다.
메모이제이션(Memoization)은 이미 계산한 결과를 저장하여 같은 상태를 재사용하는 기법으로, DFS와 결합하면 중복 연산을 줄여 성능을 크게 향상시킬 수 있습니다.

특징:

• 완전 탐색 + DP 혼합 기법
• 재귀 호출 시 이미 방문한 상태의 결과를 캐시하여 O(지수) → O(다항)으로 시간 단축
• 상태 정의가 명확해야 적용 가능

---

2. 기본 아이디어

1. DFS로 상태를 탐색
2. 상태에 대한 결과를 메모 배열(dp)에 저장
3. 이미 계산된 상태라면 저장된 값을 바로 반환
4. 모든 상태 계산 후, dp에 기록된 값 사용

---

3. 기본 코드 (Java 예시)

import java.util.*;

public class Main {
    static int[][] map;
    static int[][] dp;
    static int n, m;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        map = new int[n][m];
        dp = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = sc.nextInt();
                dp[i][j] = -1; // 방문 안 함 표시
            }
        }

        System.out.println(dfs(0, 0));
    }

    static int dfs(int x, int y) {
        if (x == n - 1 && y == m - 1) return 1; // 목적지 도착
        if (dp[x][y] != -1) return dp[x][y]; // 이미 계산된 경우

        dp[x][y] = 0; // 초기화
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (map[nx][ny] < map[x][y]) { // 조건: 내리막길 예시
                dp[x][y] += dfs(nx, ny);
            }
        }
        return dp[x][y];
    }
}