[코테] 99클럽 코테 스터디 21일차 TIL - 동적계획법

Question1 - [미들러] 1로 구성된 정사각형의 부분 행렬 찾기 (Count Square Submatrices with All Ones)

 

문제설명 https://leetcode.com/problems/count-square-submatrices-with-all-ones/description/

 

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

 

Example 1:

Input: matrix =

[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
 ]

Output: 15

 

Explanation: 

• There are 10 squares of side 1.
• There are 4 squares of side 2.
• There is  1 square of side 3.
• Total number of squares = 10 + 4 + 1 = 15.

Constraints:

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

---

문제풀이

 

문제 해설

0과 1로 구성된 행렬이 주어지면, 그 행렬 안에서 1로만 구성된 정사각형을 크기별로 찾아 더하는 문제이다.

크기 1x1인 경우, 2x2인 경우, 3x3인 경우.. 등을 모두 찾아 count에 더해주어야 한다.

 

정사각형의 개수를 구할 때, 특정 꼭지점을 기준으로 하여 그것을 포함하는 정사각형의 최대 크기, 전체 1로 이루어진 정사각형의 개수를 셀 수 있다.

아래 코드를 보면, dp[i][j] 지점을, 오른쪽 아래 꼭지점으로 하는 정사각형의 최대 길이를 저장한다.

만약 (i,j)가 첫번째 열 혹은 행에 있다면, 정사각형 최대 길이는 1이 된다.

 

반면 두번째 이상의 열 혹은 행에 있다면 2 이상의 최대 길이를 가지는 것이고, 

그 경우 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 의 값이 특정 위치의 정사각형 행렬 크기가 된다 

(위쪽 방향 확장, 왼쪽 방향 확장, 왼쪽 대각선 위 방향 확장의 최대크기들을 서로 비교해 최소값을 구함) 

정사각형을 확장할 때 세 방향(위, 왼쪽, 대각선)이 모두 1이어야 하기 때문에, 현재 위치 (i,j)(i, j)(i,j)에서 끝나는 가장 큰 정사각형의 크기를 구하려면 위 세 위치의 값 중 최소값을 사용해야 한다.

class Solution(object):
    def countSquares(self, matrix):

        m, n = len(matrix), len(matrix[0])
        
        dp = [[0] * n for _ in range(m)]
        
        count = 0
        
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 1:
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        # 왼쪽, 위쪽, 왼쪽 위 대각선 값 중 최소값 + 1
                        dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                    
                    count += dp[i][j]
        
        return count