[LeetCode] 1277 Count Square Submatrices with All Ones

💡  오늘의 학습 키워드

📌  동적 프로그래밍

 

문제 설명

문제 링크 : https://leetcode.com/problems/count-square-submatrices-with-all-ones/

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

제한 사항
1. 1 <= arr.length <= 300
2. 1 <= arr[0].length <= 300
3. 0 <= arr[i][j] <= 1

 

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

dp로 풀지 않으면 시간 복잡도 문제를 해결할 수 없는 문제였습니다. 
문제 풀이 과정보다 풀이 아이디어를 생각하는게 중요했던 문제이고, DP 배열은 다음과 같이 정의됩니다.

1. DP 배열은 dp[i][j]로 주어진 matrix와 같이 초기화되며 (i, j)에서 끝나는 가장 큰 정사각형의 한 변의 길이를 나타냅니다.
2. 위처럼 정의하게 되면 dp[i][0], dp[0][j] 값들은 확정된 1x1 정사각형이 됩니다.
3. matrix에서 1인 값을 순회하면서 첫번째 행 또는 열인 경우 DP 배열에 값을 추가합니다.
4. 첫번째 행 또는 열이 아닌 경우 DP 배열에 해당 위치의 왼쪽, 위, 왼쪽 대각선 위 값 중 가장 작은 값에 1을 더한 값을 추가합니다.
5. 판별된 DP 값을 누적하여 count 변수에 더한 후 반환해줍니다.

DP 배열을 그림을 통해 보면 다음과 같습니다.
먼저 왼쪽 대각선 위의 값이 0 이므로 (1,1) 값은 0 + 1 = 1 이 됩니다.

최소 값이 전체가 1 이므로 (1, 2) 값은 1 + 1 = 2 가 됩니다.

이렇게 반복하게 되면 완성된 DP 배열은 다음과 같습니다.

 

이전 DP 배열의 정보를 이용하여 값은 누적한 결과이고, 쉽게 설명하자면 다음과 같습니다.
(i,j) 에서 끝나는 가장 큰 정사각형의 한 변의 길이가 저장되는 것이지만, 한 겹씩 레이어를 쌓는다 생각하면 쉽습니다.
완성된 DP 배열에서 1,2,3 값 모두 1x1 정사각형 레이어가 가장 아래에 쌓여 있고,
2,3 값이 저장된 인덱스에는 그 다음 2x2 정사각형 레이어가 그 다음 층에 쌓여 있고,
3값이 저장된 인덱스 위치가 3x3 정사각형 레이터가 가장 위에 쌓여있는 방식으로 구현된 것입니다.

풀이 아이디어를 이해하면 반복문을 통해 경우의 수를 계산하는 방식이 얼마나 비효율적인지 알 수 있습니다.
문제 의도가 DP를 잘 사용해서 풀어보라는 의도였고, 결과적으로 효율적인 방식을 찾을 수 있었습니다.

 

💡 내가 해결한 방식은?

동적 프로그래밍을 이용한 풀이 (442ms)

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        n, m = len(matrix), len(matrix[0])
        dp = [[0]*m for _ in range(n)]
        cnt = 0
        
        for i in range(n):
            for j in range(m):
                if matrix[i][j] == 1:
                    if i == 0 or j == 0:
                        dp[i][j] += 1
                    else:
                        dp[i][j] += min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                
                cnt += dp[i][j]
        
        return cnt

 

---

✍️  TIL

DP 자체가 이전의 정보를 이용하여 푼다는 것은 알고 있지만 DP 배열을 어떤 조건으로 사용할 지를 구상하는게
난이도가 굉장히 높아 상당한 사고력을 필요로 하는 것 같다. 특히 이번 문제에서 나는 DP로 어떻게 구현 할지 고민 했지만
저렇게 matrix 배열과 동일한 배열을 생각한게 아니라 Square의 크기 별로 값을 저장해야겠다고 생각한거부터가
접근 방식이 잘못되었다. 그리고 한 차원 더 들어가서 DP 배열을 생성하고 나서도 모든 배열을 탐색하는 것이 아니라 
가장 최근의 왼쪽, 위, 왼쪽 위 대각선의 DP 값만 확인하여 현재 DP 배열 값을 구한다는 발상이 AI 모델링에서도
최근 기억만 사용하는 형태로 이루어지는 로직이라 정답을 알고 나서 감탄했던 것 같다.
문제 자체가 재밌었고, DP 형태로 풀이할 때 DP 배열의 정의부터 접근을 신중하게 해야 한다는 것을 알았다.
많이 풀면 또 괜찮아지겠지..원영적 사고..!