Leetcode 1277 Count Square Submatrices with All Ones (Java)

https://leetcode.com/problems/count-square-submatrices-with-all-ones/

 

 

class Solution {
    public int countSquares(int[][] matrix) {
        
        int ans=0;


        int[][] dp=new int[matrix.length][matrix[0].length];

        for (int i = 0; i < matrix.length; i++) {
            dp[i][0] = matrix[i][0];
            ans += dp[i][0];
        }

        for (int j = 1; j < matrix[0].length; j++) {
            dp[0][j] = matrix[0][j];
            ans += dp[0][j];
        }

        for(int i = 1; i < matrix.length; i++) {
            for(int j = 1; j < matrix[0].length; j++) {
                if(matrix[i][j] == 1) {
                    dp[i][j] = 1 + Math.min(Math.min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]);
                }
                ans += dp[i][j];
            }
        }


        return ans;
    }
}

1. 문제

0과 1로 이루어진 n*m의 배열이 주어질 때, 1로 만들 수 있는 정사각형의 개수를 구하라.

2. 풀이

dp[i][j]: (i, j)를 우측 하단으로 취급해 만들 수 있는 정사각형의 개수라 하자.

        int[][] dp=new int[matrix.length][matrix[0].length];

        for (int i = 0; i < matrix.length; i++) {
            dp[i][0] = matrix[i][0];
            ans += dp[i][0];
        }

        for (int j = 1; j < matrix[0].length; j++) {
            dp[0][j] = matrix[0][j];
            ans += dp[0][j];
        }

우선 맨 위, 맨 왼쪽의 dp 배열을 초기화해준다.

만약 (i, j), (i, j+1), (i+1, j)가 모두 정사각형이라면 (i+1, j+1)을 우측 하단으로 하여 정사각형을 만들 수 있다. 그렇게 되면 (i+1, j+1)을 우측 하단으로 하여 만들 수 있는 정사각형은 변의 길이가 1, 2인 정사각형, 총 2개를 만들 수 있다. 이를 늘려 해결할 수 있다.

위 예시를 살펴보자. 2번째 부터는 dp 배열이다. 모서리를 먼저 계산, (1, 1)의 위치는 1이 담겨있으니 1이 들어간다. 이제 (1, 0), (1, 1), (2, 0)에서 모두 정사각형을 만들 수 있으므로 (2, 1)에 담겨있는 1을 합쳐 길이가 2인 정사각형을 만들 수 있는 것이다.

        for(int i = 1; i < matrix.length; i++) {
            for(int j = 1; j < matrix[0].length; j++) {
                if(matrix[i][j] == 1) {
                    dp[i][j] = 1 + Math.min(Math.min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]);
                }
                ans += dp[i][j];
            }
        }

이를 기반으로 다음의 점화식을 세울 수 있다.

• dp[i][j]=min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])+1

이전에 만들 수 있는 가장 작은 정사각형에 현재 위치의 길이 1짜리 정사각형의 수를 더해준다.