LeetCode (C/C++) 1277. Count Square Submatrices with All Ones

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

---

풀이

주어진 배열을 DP 배열로 사용, 해당 위치를 오른쪽 아래로 하는 사각형의 개수를 크기와 상관 없이 구한다.

현재 위치가 사각형이 될 수 있을 때, 왼쪽 대각선/왼쪽/위를 확인 후 가장 작은 값을 구한 후 + 1

주어진 배열[i][j] = 현재 위치가 포함된 크기 1 이상의 사각형의 개수 + 크기가 1이고 현재 위치인 사각형의 개수이므로

위의 값을 계속 더해 만들 수 있는 총 사각형의 개수를 구한다

---

코드

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int row = matrix.size(), col = matrix[0].size();
        int cnt = 0;

        // 가장 윗 줄
        for (int i = 0; i < row; i++)
            cnt += matrix[i][0];

        // 가장 왼쪽 줄
        for (int j = 1; j < col; j++)
            cnt += matrix[0][j];

        // (1, 1) ~ (n - 1 ~ n - 1) 까지 현재 위치에서의 사각형의 개수 구하기
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (!matrix[i][j]) continue;
                matrix[i][j] = min(matrix[i - 1][j - 1], min(matrix[i - 1][j], matrix[i][j - 1])) + 1;
                cnt += matrix[i][j];
            }
        }
        return cnt;
    }
};