[LeetCode] 1277. Count Square Submatrices with All Ones

https://leetcode.com/problems/count-square-submatrices-with-all-ones/description/?envType=daily-question&envId=2024-10-27

leetcode - Count Square Submatrices with All Ones

문제 유형: 다이나믹 프로그래밍, 행렬

문제 난이도: Medium

 

문제

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

m * n의 크기의 0과 1로만 이루어진 행렬이 있다. 몇 개의 1로만 이루어진 정사각형 부분행렬이 존재하는지 구하시오.

 

풀이

우선, 1인 칸 하나하나는 각각 자신, 즉 1x1의 부분행렬이라고 할 수 있다.

dp[i][j] = (i, j)를 bottom-right로 하는 정사각형 부분행렬의 개수로 저장할 것이다.

 

1행 1열을 주목하자. i행 j열을 끝으로 하는 정사각형을 만들기 위해서는, (i-1, j), (i, j-1), (i-1, j-1)의 칸들이 채워져 있어야 한다.

즉, 최대로 만들 수 있는 정사각형의 개수는 이전 오른쪽 아래칸들 만들 수 있는 정사각형의 개수 + 1이다. +1을 하는 이유는, 1x1을 새로 추가한다는 의미이고, 이전 개수는 이전 정사각형들의 교집합들에 자신의 행,열까지 추가해서 새로 만들었다는 의미이다.

 

그리고, 기본 케이스로, 0행 또는 0열이면 무조건 1이다.(자기 자신)

 

누적값들을 모두 더해주면 된다.

 

코드

C++

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        int ans = 0;

        vector<vector<int>> dp(n, vector<int>(m, 0));

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (i == 0 || j == 0) {
                    dp[i][j] = matrix[i][j];
                } else if (matrix[i][j] == 1) {
                    dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
                }
                ans += dp[i][j];
            }
        }

        return ans;
    }
};