릿코드 Maximal Square

2021-01-12

DP, 릿코드

1. leetcode maximal square

1.1. 문제

Given an m x n binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

1.1.1. Example 1:

Input: matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]
Output: 4

1.1.2. Example 2:

Input: matrix = [[“0”,“1”],[“1”,“0”]]
Output: 1

1.1.3. Example 3:

Input: matrix = [[“0”]]
Output: 0

1.1.4. Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] is ‘0’ or ‘1’.

1.2. 컴퓨팅적 사고

(1) dynamic programming : bottom up 방식으로 왼쪽 상단 모서리 값을 기준으로 정사각형을 만들수있는 값을 체크해나가는 규칙을 찾아내면서 최대 사각형의 넓이를 구할 수 있습니다.
(2) 왼쪽 상단 모서리의 값이 ‘1’ 즉, 포함가능한 값일 경우에 값을 캐시하여 구해줍니다.
가장 먼저 Math.min()함수를 이용하여 왼쪽하단, 우측상단의 대각선을 비교하고 왼쪽 상단의 모서리의 값중 최솟값구해줍니다.
그리고 최솟값+1을 해주는 이유는 최대 정사각형의 길이를 구해주기 위해서 입니다. 그리고 현재 값과 비교하여 길이의 최댓값을 갱신시켜줍니다.

1.2.1. DP 예시

Input value for matrix:

1
2
3

[1, 0, 1, 1]
[1, 1, 0, 1]
[1, 1, 1, 1]

다음과 같은 입력값이 들어왔을때, 어디서부터 기준을 잡고 들어가야할지를 고민해야합니다.
정사각형이라는 조건을 만족하기위해서는 1 x 1, 2 x 2, 3 x 3 .... n x n의 범위의 만족해야합니다.

[1(1), 0(2), 1(3), 1]
[1(2), 1(2), 0(3), 1]
[1(3), 1(3), 1(3), 1]
[1, 0(1), 1(2), 1(3)]
[1, 1(2), 0(2), 1(3)]
[1, 1(3), 1(3), 1(3)]

다음과 같이 전체의 경우중에 예시로 두가지 경우를 생각해보면 왼쪽상단의 모서리값을 기준으로 정사각형이 형성되는 규칙을 발견하실 수 있습니다. 하지만, 0이 하나라도 포함되어있으면 정사각형을 형성할 수 없습니다.

1 2	[ 1 1 ] [ 1 1 ]

의 경우를 살펴보면 해당 경우는 최대 길이 2까지의 정사각형의 넓이 2*2를 구할 수 있게됩니다. 이것의 규칙을 살펴보면 값의 최솟값 + 1의 값이 해당 정사각형의 길이를 나타내는 것을 알 수 있습니다.
즉,왼쪽하단의 값, 우측상단의값의 최솟값을 구하여 왼쪽 상단모서리의 값중에서 가장 최소인값의 + 1을 해주게 되면 오른쪽상단 모서리에 해당 범위에서 구할 수 있는 정사각형의 길이를 저장해나가면 계속해서 왼쪽상단의 모서리를 기준으로 비교하는 규칙을 발견할 수 있습니다.

answer :

[0, 0, 0, 0, 0]
[0, 1, 0, 1, 1]
[0, 1, 1, 0, 1]
[0, 1, 2, 1, 1]

시간복잡도

O(N*M)

1.3. 소스코드

public class leetcode_maximal_square_kgh {
    public static void main(String[] args) {
        maximalSquare(new char[][]{
                {'1','0','1','1'},
                {'1','1','0','1'},
                {'1','1','1','1'}});

        maximalSquare(new char[][]{
                {'1','0','1','0','0'},
                {'1','0','1','1','1'},
                {'1','1','1','1','1'},
                {'1','0','0','1','0'}});

    }
    static int maximalSquare(char[][] matrix) {
        if(matrix.length == 0) return 0;
        int n = matrix.length;
        int m = matrix[0].length;
        int answer = 0;
        int[][] dp = new int[n+1][m+1];
        for (int i = 1 ; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                //왼쪽 상단 모서리값을 기준으로 '1'을 포함하고 있을 경우
                if(matrix[i-1][j-1] == '1') {
                    // 왼쪽하단, 우측상단의 대각선을 비교하고 왼쪽 상단의 모서리의 값중 최솟값구해줍니다. +1을 해주는 이유는 최대 정사각형의 길이를 구해주기 위해서 입니다.
                    dp[i][j] = Math.min(Math.min(dp[i][j-1] , dp[i-1][j-1]), dp[i-1][j]) + 1;
                    answer = Math.max(dp[i][j], answer); // update result
                }
            }
        }
        return answer*answer;
    }
}

Algorithmleetcode