Leetcode 1277. Count Square Submatrices with All Ones

문제

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

0과 1로 이루어진 m * n 그리드가 주어진다.
얼마나 많은 1로만 이루어진 정 사각형을 만들수 있을까?

예시

흰색이 0, 검은색이 1이다.

• 1 * 1 총 10개
• 2 * 2 총 4개
• 3 * 3 총 1개
• 총 15개의 정사각형을 만들수 있다.

제한

• $1 <= arr.length <= 300$
• $1 <= arr[0].length <= 300$
• $0 <= arr[i][j] <= 1$

풀이

• 자신을 오른쪽 아래 끝으로 하는 정사각형이 몇개가 만들어지는지를 계속 확인하면 된다.

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        ROW = len(matrix)
        COL = len(matrix[0])

        one = [[0] * COL for _ in range(ROW)]
        ans = 0

        for r in range(ROW):
            for c in range(COL):
                if matrix[r][c] == 1:
                    if r == 0 or c == 0:
                    	# 첫 행이나 열의 경우 사이즈가 1인것밖에 만들수 없다.
                        one[r][c] = matrix[r][c]
                    else:
                    	# 이 외의 경우 자신을 기준으로 옆과 대각선의 최소값 을 기준으로 자기 자신 ( 1 사이즈 ) 를 더한다.
                        one[r][c] = min(one[r-1][c], one[r][c-1], one[r-1][c-1]) + 1
                    ans += one[r][c]
        return ans