1277. Count Square Submatrices with All Ones

문제

풀이

아이디어

첫 번째 시도 (TLE): O(n⁵) 브루트포스

변의 길이 side를 1부터 min(m, n)까지 순회하고, 각 (i, j)를 좌상단으로 하는 side×side 서브 행렬을 전부 확인하는 5중 for문으로 구현했다. 정확하게 동작하지만 시간 초과가 발생한다. (O(n⁵)이면 당연하다...)

두 번째 시도: DP O(m×n)

dp[i+1][j+1]를 matrix[i][j]를 우하단 꼭짓점으로 하는 all-ones 정사각형의 개수로 정의한다.

matrix[i][j] === 0이면 dp[i+1][j+1] = 0
matrix[i][j] === 1이면 dp[i+1][j+1] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

세 이웃 중 가장 작은 값이 병목이 되어 정사각형 개수가 결정된다.

첫 행/열은 이웃이 없어 별도로 처리해줘야 했는데, dp 배열을 (m+1)×(n+1) 크기로 만들고 0으로 채워두면 동일한 점화식으로 처리할 수 있었다.

코드

function countSquares(matrix: number[][]): number {
  const m = matrix.length;
  const n = matrix[0].length;
  // dp[i][j]: matrix[i][j]를 우하단 꼭짓점으로 하는 정사각형의 개수
  // 첫 행/열 처리를 위해 한칸 더 크게 만듦
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  let answer = 0;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (matrix[i - 1][j - 1] === 0) dp[i][j] = 0;
      else dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
      answer += dp[i][j];
    }
  }

  return answer;
}

시간 / 공간 복잡도

시간 복잡도: O(m * n) — 행렬의 모든 셀을 한 번씩 순회
공간 복잡도: O(m * n) — dp 배열