TIL

[코테연습] 1277. Count Square Submatrices with All Ones

크라00 2024. 10. 31. 15:38

- DP / 배열 / 행렬 문제

 

https://leetcode.com/problems/count-square-submatrices-with-all-ones/description/?envType=daily-question&envId=2024-10-27

 

1. 문제 분석

  • 목적: 주어진 2D 행렬에서 모든 요소가 1로 이루어진 정사각형 서브매트릭스의 개수를 찾는 것입니다.
    • 행렬의 크기는 n x m이고, 각 위치는 0 또는 1의 값을 가집니다.
    • 각 정사각형의 크기는 1x1, 2x2, 3x3, ... 과 같이 다양한 크기가 있을 수 있습니다.
  • 문제에서 주의해야 할 점:
    • 행렬의 모든 요소가 1이어야 해당 위치가 포함된 정사각형 서브매트릭스로 인정됩니다.
    • 각 요소 (i, j)는 해당 위치를 우측 하단 꼭짓점으로 하는 정사각형 서브매트릭스의 최대 크기를 고려해야 합니다.
    • 문제는 모든 가능한 크기의 정사각형 서브매트릭스를 찾아 개수를 누적하는 것입니다.

 

2. 문제 풀이

동적 계획법 (DP) 접근

  1. DP 배열 정의:
    • dp[i][j]: 위치 (i, j)를 우측 하단 꼭짓점으로 하는 가장 큰 정사각형 서브매트릭스의 한 변의 길이를 저장합니다.
      • 예를 들어, dp[i][j] = 3이면 (i, j)를 우측 하단으로 갖는 3x3 정사각형이 존재한다는 의미입니다.
  2. 초기화 및 조건:
    • 행렬의 첫 행이나 첫 열에 있는 값들은 해당 값이 1인 경우에 1x1 정사각형을 형성합니다.
      • 즉, 첫 행과 첫 열의 dp[i][j] 값은 행렬의 해당 값(matrix[i][j]) 그대로 복사됩니다.
  3. 점화식:
    • 만약 matrix[i][j] == 1이면:
      • dp[i][j]는 그 위치에서 만들 수 있는 가장 큰 정사각형의 크기를 의미하며, 다음과 같은 점화식을 사용합니다:
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

 

      • 여기서 dp[i-1][j], dp[i][j-1], dp[i-1][j-1]는 각각 현재 위치의 위쪽, 왼쪽, 왼쪽 위 대각선에 있는 값들입니다.
      • 이 중에서 가장 작은 값을 선택하고 +1을 더해서 현재 위치의 정사각형 크기를 결정합니다.
      • 예를 들어, (i, j) 위치에서 위쪽, 왼쪽, 대각선 위의 값이 모두 2라면, (i, j)를 포함한 3x3 정사각형이 만들어질 수 있습니다.
  • 정사각형 개수 누적:
    • 각 위치에서 계산된 dp[i][j] 값을 total 변수에 더해 모든 정사각형의 개수를 누적합니다.
    • dp[i][j]가 3이라면 (i, j)를 우측 하단 꼭짓점으로 하는 1x1, 2x2, 3x3 총 3개의 정사각형이 있다는 의미입니다.
  • 반복문을 통한 계산:
    • 2중 반복문을 통해 행렬의 모든 위치 (i, j)에 대해 위의 과정을 수행합니다.
    • 행렬의 모든 요소를 순회하며, 각 요소가 우측 하단 꼭짓점인 정사각형의 크기를 계산하고 그 개수를 누적합니다.

 

요약

  • 문제 분석: 주어진 2D 행렬에서 모든 요소가 1인 모든 크기의 정사각형 서브매트릭스의 개수를 찾는 문제입니다.
  • 문제 풀이:
    1. DP 배열 정의: dp[i][j]는 위치 (i, j)를 우측 하단 꼭짓점으로 하는 가장 큰 정사각형의 크기를 나타냅니다.
    2. 점화식 사용: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1로 각 위치에서 만들 수 있는 최대 정사각형의 크기를 계산합니다.
    3. 정사각형 개수 누적: 모든 dp[i][j] 값을 누적하여 전체 정사각형의 개수를 구합니다.
    4. 시간 복잡도: O(n * m)으로 효율적으로 문제를 해결합니다.

 

 

> java

 

class Solution {
    public int countSquares(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;

        int[][] dp = new int[n][m];
        int total = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] != 1) {
                    continue;
                }
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                }
                total += dp[i][j];
            }
        }

        return total;
    }
}

 

 

 

> python

 

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

        dp = [[0] * m for _ in range(n)] 

        total = 0

        for i in range(n) :
            for j in range(m) :
                if matrix[i][j] == 0 :
                    continue
                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
                total += dp[i][j]

        return total