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

Main.java

import java.io.*;
import java.util.*;

public class Main {

    static int n;
    static int[][] grid;
    static int[][] dp;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int answer;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        grid = new int[n][n];
        dp = new int[n][n];

        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[2], o2[2]));
        for (int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            Arrays.fill(dp[i], 1);
            for (int j=0; j<n; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
                pq.offer(new int[]{i, j, grid[i][j]});
            }
        }

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int x = cur[0];
            int y = cur[1];
            int num = cur[2];

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

                if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
                    continue;
                }

                if (num < grid[nx][ny]) {
                    dp[nx][ny] = Math.max(dp[nx][ny], dp[x][y] + 1);
                }
            }

            answer = Math.max(answer, dp[x][y]);
        }

        sb.append(answer);

        bw.write(sb.toString());
        bw.close();
        br.close();
    }
}