[스파르타] 99클럽 2기 코테스터디 21일차 TIL / leet 1277

Leetcode: 1277. Count Square Submatrices with All Ones (링크)

 

1277. Count Square Submatrices with All Ones

 

입력값으로 0, 1로 구성된 행렬이 주어지고 여기에서 모든 하위 사각형의 개수를 구하는 문제이다. 모든 행렬 요소를 for문으로 돌면서 처음에는 길이가 1인 사각형만 찾고 루프가 종료되면 다음에는 길이가 2인 사각형, 다음은 길이가 3인 사각형, ... 이런 식으로 루프를 더 이상 해당 길이의 사각형을 구하지 못할 때까지 계속 돌면 구할 수 있다. 그러나 시간이 오래 걸리고 비효율적인 방법이다. 따라서 기존 행렬을 for문으로 한 번만 돌면서 해당 위치에서 가능한 사각형 길이 개수를 갱신하는 방법으로 진행한다.

 

 

0번째 행과 열은 해당 위치에서 길이가 1인 사각형만 구할 수 있다. 그러므로 시작하는 위치는 1행, 1열의 요소에서부터다. 위의 이미지에서 빨간색 사각형으로 표시한 부분이 for문의 현재 위치다. 노란색 사각형으로 표시한 부분이 빨간색 사각형의 숫자를 갱신할지 말지 정하는 요소들이다. 만약 노란색 사각형 안에 0이 포함되어 있다면 길이가 2인 사각형은 만들 수 없다. 그러므로 그 다음 요소로 빨간색 사각형이 이동한다. 노란색 사각형 안에 0보다 큰 수만 있다면 그 중 최솟값을 빨간색 사각형 숫자에 더해서 갱신해준다. 

 

이런 식으로 모든 for문을 돌면서 행렬 안의 숫자들을 더해주면 만들 수 있는 모든 사각형의 종류를 구할 수 있게 된다.

 

풀이 설명

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        height = len(matrix) # 행
        width = len(matrix[0]) # 열
        cnt = 0 # 모든 사각형 개수

        # 0번째 인덱스 행 모두 더하기
        for col in range(width):
            cnt += matrix[0][col]

        # 0번째 인덱스 열 모두 더하기
        for row in range(1, height):
            cnt += matrix[row][0]

        # [1, 1]부터 [height-1, width-1]까지 계산하기
        for row in range(1, height):
            for col in range(1, width):
                if matrix[row][col] == 1 and matrix[row-1][col] > 0 and matrix[row][col-1] > 0 and matrix[row-1][col-1] > 0:
                    matrix[row][col] += min(matrix[row-1][col], matrix[row][col-1], matrix[row-1][col-1])
                cnt += matrix[row][col]
        return cnt

 

오늘 미들러 풀이 끝!

---

참고한 풀이: https://www.youtube.com/watch?v=JSOL4UGjBzc