1277. Count Square Submatrices with All Ones

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

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:05:29

 

---

 

문제 설명

 

오늘은 조금 색다른 흰색 배경

0 혹은 1로 구성된 m * n 행렬이 주어질때, 모든 값이 1로 이루어진 정사각 부분행렬의 개수를 반환하라. 

---

 

풀이

 

정사각형의 개수를 새는 DP 문제는 꽤나 자주 빈출되는 문제이다(이제는 공식처럼 외워 쓸 수 있을 정도로 자주 보이기에, DP 문제의 숙련도를 쌓기에는 그리 추천하지 않는다.

 

2023.02.21 - [PS/백준] - [백준/1460] 진욱이의 농장 (Python3)

[백준/1460] 진욱이의 농장 (Python3)

 

 

2023.05.19 - [분류 전체보기] - [백준/1915] 가장 큰 정사각형 (python)

[백준/1915] 가장 큰 정사각형 (python)

 

위 문제들을 바라보면서, 이 문제는 정사각형 DP로 풀어보자! 고 생각해보자.

 

그럼 풀이를 더욱 쉽게 떠올릴 수 있다. DP[Y][X]를 오른쪽 아래 좌표가 (X,Y)인 정사각형 중 제일 큰 정사각형의 변의 길이라고 정의하자. 수식상으로는

• DP[Y][X] = 0 (matrix[Y][X] = 0일 경우)
• DP[Y][X] = min(DP[Y-1][X], DP[Y][X-1], DP[Y-1][X-1]) + 1 (matrix[Y][X] > 0일 경우)

가 성립한다. 

예전 풀이 울궈먹기

위 사각형을 생각해보면 이해가 좀 더 편하다. 만약 dp[i][j] (=DP[Y][X])가 정사각형이라면, 위 세 영역중 제일 값이 작은 값(2)을 기준으로 새로 최대 정사각형을 그릴 수 있다.

이런 식으로 DP가 정의되며, 이 과정이 직관적으로 이해될것이다.

또, DP[Y][X] = n이라면 오른쪽 아래 좌표가 (X,Y)인 정사각형이 변의 길이 1부터 n까지 존재할 수 있다.

 

따라서 본 질문은 DP matrix를 구하고, 그 matrix의 총합을 구하는 문제로 바꿀 수 있다. 시간복잡도는 O(N^2)이다.

 

풀이 코드

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        X, Y = len(matrix[0]), len(matrix)
        dp = [[0]*X for _ in range(Y)]
        result = 0

        for y in range(Y) :
            for x in range(X) :
                if matrix[y][x] :
                    result += 1
                    dp[y][x] = 1
                    if y > 0 and x > 0 :
                        minlen = min(dp[y-1][x], dp[y][x-1], dp[y-1][x-1])
                        result += minlen
                        dp[y][x] = max(dp[y][x], minlen+1)
        return result

 

풀이 코드 (좀 더 공간 효율적인 버전)

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

        for y in range(1, Y) :
            for x in range(1, X) :
                if matrix[y][x] :
                    matrix[y][x] += min(matrix[y-1][x], matrix[y][x-1], matrix[y-1][x-1])

        return sum(map(sum, matrix))