LeetCode 221 - Maximal Square (Medium)

문제

LeetCode - 221번

풀이 과정

주어진 martix 안에서 가장 큰 정사각형을 찾는 문제입니다.
각각의 정사각형은 또다른 정사각형으로 구성되어 있다는 점을 통해 동적 계획법 으로 풀이가 가능한 문제입니다.

따라서 dp(x, y) = (x, y)를 왼쪽 모서리로 하는 최대 정사각형의 한 변의 길이 라고 정의한다면
다음과 같은 점화식을 세울 수 있습니다.

dp(x,y) = 0 if board[x][y] == 0 else min(dp(x+1, y), dp(x+1, y+1), dp(x, y+1)) + 1

이때 board 의 각 지점을 순회하며 1이 발견될때마다 dp 를 호출하며 최대값을 갱신하면 원하는 결과를 얻을 수 있습니다.

코드

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function (matrix) {
  if (matrix.length === 0) {
    return 0;
  }
  const H = matrix.length;
  const W = matrix[0].length;

  const memo = new Array(H).fill(null).map((_) => new Array(W).fill(-1));

  function dp(x, y) {
    if (x < 0 || x >= H || y < 0 || y >= W) {
      return 0;
    }

    if (memo[x][y] !== -1) {
      return memo[x][y];
    }

    if (matrix[x][y] === "1") {
      memo[x][y] = Math.min(dp(x + 1, y), dp(x + 1, y + 1), dp(x, y + 1)) + 1;
    } else {
      memo[x][y] = 0;
    }

    return memo[x][y];
  }

  // 가장 큰 정사각형을 찾는다.
  let ans = 0;
  for (let x = 0; x < H; x++) {
    for (let y = 0; y < W; y++) {
      if (matrix[x][y] === "1") {
        ans = Math.max(ans, dp(x, y));
      }
    }
  }

  return ans * ans;
};

const matrix = [
  ["1", "1", "1", "1", "1"],
  ["1", "0", "1", "1", "1"],
  ["1", "1", "1", "1", "1"],
  ["1", "0", "0", "1", "0"],
];
console.log(maximalSquare(matrix));