[LeetCode- Part. 4] 4. 최대 정사각형 # (+ 2차원 DP)

 

 

 

https://leetcode.com/problems/maximal-square/

Maximal Square - LeetCode

 

 

규칙을 찾아서 DP 배열을 작성한다.

---

class Solution {
    public int maximalSquare(char[][] matrix) {
        //1. ds
        int m = matrix.length;
        int n=matrix[0].length;
        
        //DP에서 필요한 길이만큼 배열 생성
        int[][] dp = new int[m+1][n+1];
        int maxSize= 0;
        
        //2. loop
        //1번칸 부터 시작해, i-1 j-1칸에 채운다.
        for(int i=1; i<=m;i++){
            for(int j=1;j<=n;j++){
                //첫 번째 사각형의 경우 : matrix[1][1] ->  dp[2][2]=2가 된다.
                if(matrix[i-1][j-1] == '1'){
                    //int min=Math.min(dp[2][1], dp[1][2]);
                    int min=Math.min(dp[i][j-1], dp[i-1][j]);
                    //가능한 사각형의 최솟값이므로, dp[2][1]과 dp[1][2]의 최솟값을 선택해, dp[1][1]과 비교해 작은 값 선택해 +1
                    dp[i][j]=Math.min(min, dp[i-1][j-1])+1;
                    
                    //최대 사각형 개수 갱신
                    maxSize=Math.max(maxSize, dp[i][j]);
                }
            }
        }
        //사격형의 개수 이므로, 최대 크기의 제곱
        return maxSize*maxSize;
    }
}

---

+) 연관 문제

https://leetcode.com/problems/maximal-rectangle/

Maximal Rectangle - LeetCode