Programmers - 가장 큰 정사각형 찾기 with JAVA (V)

 

 

문제

0, 1로 이루어진 2차원 배열이 주어진다. 이 때, 1로만 이루어진 정사각형의 넓이 중 가장 큰 넓이를 반환하라.

 

 

 

 

로직

해당 문제는 DP로 해결을 했다. 처음에는 DP를 항상 일차원적으로만 해석해왔기에 DP라는 아이디어를 떠올리기조차 어려웠다. 하지만 완탐을 하기에는 시간복잡도를 고려해보았을 때, 불가능하다.

DP 아이디어는 "현재 x,y좌표에 맞는 최대 넓이는 (x-1, y), (x, y-1), (x-1, y-1)에 해당 하는 값의 최소값 + 1이다."

 

예를 들어보면, 아래와 같은 2차원 배열이 있다고 가정하자.

매번 1이 나올때마다 체크한다.

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

(0, 1)까지의 최대 넓이는 1이다.

(0, 2)까지의 최대 넓이는 1이다.

(0, 3)까지의 최대 넓이는 1이다.

 

(1, 0)까지의 최대 넓이는 1이다.

(1, 1)까지의 최대 넓이는 1이다.

(1, 2)까지의 최대 넓이는 2이다. (이유는 DP상 위에서 말한 인덱스의 값이 모두 1이다. 즉, 넓이가 4가 될 수 있다.)

(1, 3)까지의 최대 넓이는 2이다. (이하 동문)

 

(2, 0)까지의 최대 넓이는 1이다.

(2, 1)까지의 최대 넓이는 2이다.

(2, 2)까지의 최대 넓이는 2이다.

(2, 3)까지의 최대 넓이는 3이다. (이유는 DP상 위에서 말한 인덱스의 값이 모두 2이다. 즉, 넓이가 9가 될 수 있다.)

 

(0, 2)까지의 최대 넓이는 1이다.

 

 

 

이 때, DP를 보면 아래와 같다.

1. 우선, DP맵의 x축과 y축의 길이를 1씩 늘린다.

2. 위에서 설명한 인덱스 중 최소값을 구한다.

3. 그 값에 1을 더한 값이 현재 DP의 값이 된다.

4. 매 순간 값들 중 최대값을 구하고 그 값의 제곱이 정답이 된다.

0 0 0 0 0  
0 0 0 0 0  
0 0 0 0 0  
0 0 0 0 0  
0 0 0 0 0  

0 0 0 0 0  
0 0 1 0 0  
0 0 0 0 0  
0 0 0 0 0  
0 0 0 0 0  
 
0 0 0 0 0  
0 0 1 1 0  
0 0 0 0 0  
0 0 0 0 0  
0 0 0 0 0  
 
0 0 0 0 0  
0 0 1 1 1  
0 0 0 0 0  
0 0 0 0 0  
0 0 0 0 0  
 
0 0 0 0 0  
0 0 1 1 1  
0 1 0 0 0  
0 0 0 0 0  
0 0 0 0 0  
 
0 0 0 0 0  
0 0 1 1 1  
0 1 1 0 0  
0 0 0 0 0  
0 0 0 0 0  
 
0 0 0 0 0  
0 0 1 1 1  
0 1 1 2 0  
0 0 0 0 0  
0 0 0 0 0  
 
0 0 0 0 0  
0 0 1 1 1  
0 1 1 2 2  
0 0 0 0 0  
0 0 0 0 0  
 
0 0 0 0 0  
0 0 1 1 1  
0 1 1 2 2  
0 1 0 0 0  
0 0 0 0 0  
 
0 0 0 0 0  
0 0 1 1 1  
0 1 1 2 2  
0 1 2 0 0  
0 0 0 0 0  
 
0 0 0 0 0  
0 0 1 1 1  
0 1 1 2 2  
0 1 2 2 0  
0 0 0 0 0  
 
0 0 0 0 0  
0 0 1 1 1  
0 1 1 2 2  
0 1 2 2 3  
0 0 0 0 0  
 
0 0 0 0 0  
0 0 1 1 1  
0 1 1 2 2  
0 1 2 2 3  
0 0 0 0 0  
 
0 0 0 0 0  
0 0 1 1 1  
0 1 1 2 2  
0 1 2 2 3  
0 0 0 0 0  
 
0 0 0 0 0  
0 0 1 1 1  
0 1 1 2 2  
0 1 2 2 3  
0 0 0 1 0  
 
0 0 0 0 0  
0 0 1 1 1  
0 1 1 2 2  
0 1 2 2 3  
0 0 0 1 0

 

 

좀 더 설명을 하자면 예를 들어, 넓이 9의 정사각형을 만들려면 넓이 4의 정사각형 3개가 상, (상좌), 좌에 있어야하는 원리이다.

 

 

 

 

코드

class Solution{
    public int solution(int[][] board){
        int[][] dp = new int[board.length+1][board[0].length+1];
        int answer = 0;
        for(int x=1; x<board.length+1; x++){
            for(int y=1; y<board[0].length+1; y++){
                if(board[x-1][y-1] == 1){
                    dp[x][y] = Math.min(dp[x-1][y], dp[x][y-1]);
                    dp[x][y] = Math.min(dp[x-1][y-1], dp[x][y]) + 1;
                    answer = Math.max(answer, dp[x][y]);
                }
            }
        }
        return answer*answer;
    }
}

 

 

 

조금 더 직관적인 코드

- answer의 초기값은 board가 모두 0인 경우를 대비해 0으로 초기화해야함을 주의하자.

class Solution{
    public int solution(int[][] board){
        int answer = 0;
        int[][] dp = new int[board.length][board[0].length];
        for(int x=0; x<board.length; x++){
            for(int y=0; y<board[0].length; y++){
                if(board[x][y] == 0){
                    continue;
                }
                if(x == 0 | y == 0){
                    dp[x][y] = board[x][y];
                    continue;
                }
                int min_value = Math.min(dp[x-1][y], dp[x][y-1]);
                min_value = Math.min(min_value, dp[x-1][y-1]);
                dp[x][y] = min_value+1;
                answer = Math.max(dp[x][y]*dp[x][y], answer);
            }
        }
        return answer;
    }
}