[코드 트리] 정수 사각형 최장 증가 수열 (JAVA)

[코드 트리] 정수 사각형 최장 증가 수열

🗒️알고리즘 분류

#Dynamic Programming #Memoization #Top-Down

먼저 이 문제를 풀면서 삽질한 풀이를 보여주고 이 풀이가 왜 틀렸는지를 설명해보겠다.

📝잘못된 풀이

import java.util.*;

public class Main {
    static final int UNUSED = -1;
    private static int N = 0, Answer = 0;
    static int[][] Matrix, dp;
    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();

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

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

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                Answer = Math.max(Answer, findMaxMove(i,j,1));
            }
        }

        System.out.println(Answer);
    }

    private static int findMaxMove(int x, int y, int move) {
        if (dp[x][y] != UNUSED) {
            return dp[x][y];
        }
        if (cannotMove(x,y)) {
            return move;
        }

        int maxMove = move;

        for (int dir = 0; dir < 4; ++dir) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if (isInRange(nx,ny) && Matrix[nx][ny] > Matrix[x][y]) {
                maxMove = Math.max(maxMove, findMaxMove(nx, ny, move+1));
            }
        }

        dp[x][y] = maxMove;

        return maxMove;
    }

    private static boolean cannotMove(int x, int y) {
        boolean flag = true;

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

            if (isInRange(nx,ny) && Matrix[nx][ny] > Matrix[x][y]) {
                flag = false;
            }
        }

        return flag;
    }

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

왜 이 코드가 문제인가?

1. dp[x][y]에 저장되는 값이 부모의 move에 의존
   • 코드에서 findMaxMove(x, y, move)는 재귀적으로 move+1을 전달하여 경로 길이를 누적한다.
   • 동시에, dp[x][y] = maxMove를 저장한다.
   • 그런데 만약 (x, y)에 도달하는 경로가 여러 개라면, 시작점(부모)의 move 값이 달라질 수 있다.
   • 한 번 (x,y)를 계산해 dp[x][y]에 저장한 후, 다른 경로(더 긴 혹은 더 짧은)에서 (x,y)를 다시 방문해도,이미 dp[x][y]가 채워져 있으므로 이전에 계산된 값(다른 move 기반)만을 반환하게 된다.
2. cannotMove(x,y)로 리프를 판단해도 중간 경로가 누락될 수 있음
   • 현재 코드는 cannotMove(x,y)가 true일 때에만 즉시 move를 반환한다.
   • 그러나 실제로는 "가장 긴 증가 경로"가 중간 노드에서도 더 긴 길이가 나올 수 있는데,그 로직을 이 코드에서 전부 커버하기가 어렵다.
   • 표준 접근에서는 리프 노드를 별도로 판별하지 않아도,이웃에 더 큰 값이 없으면 for문에서 갱신이 일어나지 않아 자연스럽게 길이 1이 된다.

📌기억할 만한 포인트

NxN 크기의 Matrix 에서 시작점을 적절하게 잡아서 상하좌우로 계속 인접한 칸의 정수값이 커지도록 이동할 때, 거쳐간 격자 수의 최댓값을 구하는 문제이다.

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

• dp[x][y] : (x,y) 위치에서 시작하는 최대 증가 격자수
• findMaxMove(x,y) : 함수는 현재 위치에서 이동할 수 있는 최대 길이를 반환

dp[x][y]은 중복 계산을 피하기 위한 Memoization 배열로, 이미 계산된 위치(=똑같은 값으로 재귀함수가 불릴 경우)를 저장해 빠른 결과를 제공합니다. 각 방향으로 이동하며 증가하는 숫자를 찾고, 그 경로의 길이를 업데이트하여 최종적으로 이동 가능한 최대 길이를 찾는다.

따라서 최종 목적지 없이도 각 위치에서의 최대 이동 경로를 계산하여 전체 최대 값을 구할 수 있다.

📝풀이 코드(JAVA)

import java.util.*;

public class Main {
    static final int UNUSED = -1;
    private static int N = 0, Answer = 0;
    static int[][] Matrix, dp;
    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();

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

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

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                Answer = Math.max(Answer, findMaxMove(i,j));
            }
        }

        System.out.println(Answer);
    }

    private static int findMaxMove(int x, int y) {
        if (dp[x][y] != UNUSED) {
            return dp[x][y];
        }

        int maxMove = 1;

        for (int dir = 0; dir < 4; ++dir) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if (isInRange(nx,ny) && Matrix[nx][ny] > Matrix[x][y]) {
                maxMove = Math.max(maxMove, findMaxMove(nx, ny) + 1);
            }
        }

        dp[x][y] = maxMove;

        return maxMove;
    }

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

⏰총 풀이시간

• 120분;;