[LeetCode] 221. Maximal Square

문제

 

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.

 

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

 

Example 2:

 

Input: matrix = [["0","1"],["1","0"]]
Output: 1

 

 

 

 

내 생각

 

1로 구성된 정사각형의 넓이를 구하는 문제이다. dp를 사용해서 풀면된다!

현재 위치의 값이 '1'인 경우에 가능한 가장 큰 정사각형의 변의 길이를 계산한다. 

dp[i][j] 가 (i-1, j-1) 위치에서 끝나는 가장 큰 정사각형의 한 변의 길이이다.

dp[i][j]의 값은 matrix[i-1][j-1]이 '1'일 때, dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 값 중 최소값에 1을 더한 값이다.

 

 

 

내 코드

class Solution {
    public int maximalSquare(char[][] matrix) {
        int n = matrix.length;
        if (n == 0) return 0;
        int m = matrix[0].length;

        int[] dp = new int[m + 1];
        int max = 0, prev = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int temp = dp[j]; //현재 dp[j] 값을 temp에 저장
                // 현재 위치의 값이 '1'인 경우
                if (matrix[i - 1][j - 1] == '1') {
                    // dp[j] 값을 갱신, 이전 값들 중 최소값에 1을 더함(현재 위치에서 가능한 가장 큰 정사각형의 변의 길이 계산)
                    dp[j] = Math.min(dp[j], Math.min(dp[j - 1], prev)) + 1;
                    // 최대 변의 길이 갱신
                    max = Math.max(dp[j], max);
                } else {
                    // 행렬의 현재 값이 '0'인 경우, dp[j]를 0으로 설정
                    dp[j] = 0;
                }
                // prev를 갱신하여 다음 열의 dp[j-1]로 사용
                prev = temp;
            }
        }
        // 가장 큰 정사각형의 면적 반환
        return max * max;
    }
}