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

📝 문제

문제 | 코드트리. 정수 사각형 최장 증가 수열

💡 풀이 과정

⛓ 사용한 알고리즘 : DP, BFS

우선순위 큐 이용하기

문제를 읽다가 바로 우선순위 큐를 사용해야 겠다는 생각을 하게 된 가장 큰 이유는 “출발점과 도착점이 정해져있지 않기 때문”이었다. n x n 크기의 격자에서 정수는 랜덤한 위치로 주어지며, 중복 또한 가능하다. 따라서 가장 작은 수부터 탐색을 시작한다고 했을 때 시작점이 몇 개가 될지는 알 수 없다.

때문에 각 격자칸의 좌표와 해당 위치의 정수 정보를 모두 갖고 있는 클래스를 선언한 후 해당 클래스 객체의 정수를 비교하는 우선순위 큐를 사용하면, 정수가 가장 작은 지점부터 탐색을 시작할 수 있다.

static class Point implements Comparable<Point> {
	int i,j,n;
	public Point(int i, int j, int n) {
		this.i = i;
		this.j = j;
		this.n = n;
	}
	        
	@Override
	public int compareTo(Point o) {
		return this.n-o.n;
	}
}

DP 배열 채우기

dp 배열에는 내가 현재 칸에 도달하기 까지 몇 개의 칸을 지났는지의 정보를 기록한다. 큐에서 꺼낸 좌표에서 4방향으로 탐색을 진행하며, 인접한 칸의 정수가 현재 좌표의 정수보다 큰 경우 dp 배열의 값을 더 큰 값으로 갱신해준다. 4방향 탐색이 모두 종료되면 최댓값을 주기적으로 갱신해줬는데, 이 작업은 dp 배열을 모두 채운 후 배열을 선형탐색하며 최댓값을 찾아줘도 된다.

int ans = Integer.MIN_VALUE;

while(!pq.isEmpty()) {
	Point tmp = pq.poll();
	int ti = tmp.i;
	int tj = tmp.j;
	int tn = tmp.n;
	
	for(int d=0;d<4;d++) {
		int ni = ti+di[d];
		int nj = tj+dj[d];
		
		if(ni<0 || ni>=N || nj<0 || nj>=N) continue;
		if(map[ni][nj]<=tn) continue;
		
		dp[ni][nj] = Math.max(dp[ni][nj], dp[ti][tj]+1);
	}
	ans = Math.max(dp[ti][tj], ans);
}

이 때 일반적인 BFS 탐색과는 약간 다르게 탐색을 진행하면서 객체를 큐에 넣어주지 않았는데, 처음 입력받을 때 모든 좌표를 우선순위 큐에 넣고 시작했기 때문이다. 자동적으로 정수 값이 작은 좌표부터 큐에서 빠져나오기 때문에 굳이 값을 비교해가며 우선순위 큐에 넣어주지 않아도 된다.

코드

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

public class Main {

    static int[] di = {-1,1,0,0};
    static int[] dj = {0,0,-1,1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

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

        StringTokenizer st;
        PriorityQueue<Point> pq = new PriorityQueue<>();
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                pq.offer(new Point(i,j,map[i][j]));
            }
        } //end input

        int ans = Integer.MIN_VALUE;
        while(!pq.isEmpty()) {
            Point tmp = pq.poll();
            int ti = tmp.i;
            int tj = tmp.j;
            int tn = tmp.n;

            for(int d=0;d<4;d++) {
                int ni = ti+di[d];
                int nj = tj+dj[d];

                if(ni<0 || ni>=N || nj<0 || nj>=N) continue;
                if(map[ni][nj]<=tn) continue;

                dp[ni][nj] = Math.max(dp[ni][nj], dp[ti][tj]+1);
            }

            ans = Math.max(dp[ti][tj], ans);
        }

        System.out.println(ans+1);
        
    }

    static class Point implements Comparable<Point> {
        int i,j,n;
        public Point(int i, int j, int n) {
            this.i = i;
            this.j = j;
            this.n = n;
        }
        
        @Override
        public int compareTo(Point o) {
            return this.n-o.n;
        }
    }
}