[코드 트리] 정수 사각형 차이의 최소 2 (JAVA)

[코드 트리] 정수 사각형 차이의 최소 2

🗒️알고리즘 분류

#Dynamic Programming #Memoization #Top-Down

📌기억할 만한 포인트

NxN 크기의 Matrix 에서 (1,1) 에서 시작하여 오른쪽 혹은 밑으로만 이동하여 (N,N) 으로 갈 때, 거쳐간 격자에 있는 수들 중 최댓값과 최솟값의 차이를 가장 작게 만들어야 하는 문제이다.

이렇게 보통 방향이 한쪽으로 일관성 있게 결정되어 있으면 격자 안에서 한칸씩 움직이는 dp 문제이다.
해설에서는 Tabulation(Bottom-Up)방식만 설명되어 있어서 Memoization(Top-Down)방식으로 풀어보았다.

기억할 만한 점은 총 3가지이다.

1. dp[x][y][m]: (x,y)에 도달했을 때, 경로상의 최소값이 m인 상태에서 기록된 최소의 currMax 값을 저장
   • 최솟값과 최댓값을 함께 알아야 하므로 dp 배열 중에 한개의 차원을 이용하여 입력값의 범위인 1~100 을 고려하여 new int[N][N][101] 로 선언한다.
2. int dfs(int x, int y, int currMin, int currMax): 최종 지점(N-1, N-1) 에 도착했을 때 (currMax - currMin), 즉 경로의 최댓값, 최솟값의 차이
3. dp[x][y][currMin] != -1 && dp[x][y][currMin] <= currMax: 같은 (x,y)에서 currMin 상태로 이미 더 좋은(currMax가 낮은) 값으로 방문한 적이 있다면 가지치기

• 이전 방식 (반환값과 dp가 같은 의미일 때):
  • 재귀 함수가 어떤 상태에 대해 직접 답(예: 최소 비용, 최대값 등)을 반환하고,
  • dp 배열에 그 결과를 저장해 나중에 동일한 상태가 나오면 바로 반환한다.
• 현재 방식 (dp가 가지치기용으로 사용될 때):
  • DFS 함수 dfs(x, y, currMin, currMax)의 반환값은 (n-1, n-1)까지 가는 경로의 최종 범위 차이(currMax - currMin)입니다.
  • 그러나, dp 배열은 (x,y)에 도달했을 때, 그 상태에서의 currMin(즉, 지금까지 경로의 최소값)이 동일한 경우에현재까지 도달한 경로의 최소의 currMax를 기록합니다.
  • 이렇게 기록해두면, 나중에 동일한 (x, y, currMin) 상태에 도달했을 때,이미 더 낮은 currMax를 얻은 상태가 있다면 그 상태에서는 더 이상 좋은 결과를 기대할 수 없으므로,가지치기를 통해 탐색을 중단할 수 있습니다.

📝풀이 코드(JAVA)

import java.util.*;

public class Main {
    public static final int INT_MAX = Integer.MAX_VALUE;
    
    public static int N;
    public static int[][] Matrix;
    // dp[x][y][m]: (x,y)에 도달했을 때, 경로상의 최소값이 m인 상태에서 기록된 최소의 currMax 값을 저장
    // 미방문 상태는 -1로 초기화
    public static int[][][] dp;

     public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();

        Matrix = new int[N][N];
        dp = new int[N][N][101];

        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                Matrix[i][j] = sc.nextInt();
            }
        }
        
        initializeDP();

        // (0,0)에서 시작하면, 초기 상태로 최소값과 최대값 모두 num[0][0]으로 시작
        System.out.print(dfs(0, 0, Matrix[0][0], Matrix[0][0]));
    }
    
    public static void initializeDP() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
    }
    
    /**
     * DFS로 (0,0)에서 (n-1, n-1)까지 경로를 탐색합니다.
     * @param x 현재 행 좌표
     * @param y 현재 열 좌표
     * @param currMin 현재까지 경로의 최소값
     * @param currMax 현재까지 경로의 최대값
     * @return 도착했을 때 (currMax - currMin), 즉 경로의 최댓값과 최솟값의 차이
     */
    public static int dfs(int x, int y, int currMin, int currMax) {
        if (x == N - 1 && y == N - 1) {
            // 도착지에서는 이미 최소, 최대값이 결정되어 있으므로 바로 차이를 반환
            return currMax - currMin;
        }
        // 같은 (x,y)에서 currMin 상태로 이미 더 좋은(currMax가 낮은) 값으로 방문한 적이 있다면 가지치기
        if (dp[x][y][currMin] != -1 && dp[x][y][currMin] <= currMax) {
            return INT_MAX;
        }
        dp[x][y][currMin] = currMax;
        
        int ans = INT_MAX;
        // 오른쪽과 아래로 이동 (dx,dy 사용)
        int[] dx = {1, 0};
        int[] dy = {0, 1};
        for (int d = 0; d < 2; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (isInRange(nx, ny)) {
                int newMin = Math.min(currMin, Matrix[nx][ny]);
                int newMax = Math.max(currMax, Matrix[nx][ny]);
                ans = Math.min(ans, dfs(nx, ny, newMin, newMax));
            }
        }

        return ans;
    }

    private static boolean isInRange(int x, int y) {
        return 0 <= x && x < N && 0 <= y && y < N;
    }
}

⏰총 풀이시간

• 140분;;