99클럽 코테 스터디 21일차 TIL + Array/Dynamic Programming/Matrix : count-square-submatrices-with-all-ones

문제

링크텍스트

풀이

class Solution:
    def countSquares(self, matrix):
        m = len(matrix)
        n = len(matrix[0])
        ans = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j] > 0 and i > 0 and j > 0:
                    matrix[i][j] = min(matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1]) + 1
                ans += matrix[i][j]
        return ans

• matrix를 좌에서 우로, 위에서 아래로 훑어나갑니다.
• 훑어가는 도중의 한 위치를 기준으로 하여, 그 왼쪽과 또 그 위의 영역에서 만들 수 있는 모든 정방행렬의 수를 구합니다.
• 이렇게 주어진 입력 matrix의 마지막 low의 마지막 col이 되면, 구할 수 있는 정방행렬의 모든 수를 구하겠다는 계획입니다.
• 우선 값이 1이면 1을 더할 수 있습니다.
• row 1 과 col 1은 square matrix의 갯수 합에 기여하는 것이 위의 규칙으로 끝입니다.
• 하지만 그 안쪽은 추가 기여가 가능합니다. 문제는 과연 얼마나 더 기여할 수 있을까 입니다.
• 훑어가는 도중의 한 위치에서, 만약 자신이 1이고, 왼쪽, 위, 그리고 좌상의 값이 모두 1이면, 크기 2인 정방행렬이 추가될 수 있습니다.
• 1 row, 1 col을 더 나아가 만약 그 3x3 영역이 모두 1이면, 크기 3인 정방행렬이 한 번 더 추가될 수 있습니다.
  • 달리 보면, 왼쪽, 위, 그리고 좌상이 모두 크기 2인 정방행렬의 일원이었다면, 현 위치는 크기 3인 정방행렬의 오른쪽/맨 아래 끝이었다는 얘기입니다.
• 이렇게 계속 커져갑니다.

결과