[프로그래머스] 가장 큰 정사각형 찾기

문제

가장 큰 정사각형 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/12905

 

 

예시 코드

function solution(board) {
  const n = board.length;
  const m = board[0].length;
  const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));
  let maxSide = 0;

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (board[i - 1][j - 1] === 0) continue;
      const minSide = Math.min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]);
      dp[i][j] = minSide + 1;
      maxSide = Math.max(maxSide, dp[i][j]);
    }
  }

  return maxSide ** 2;
}

 

 

풀이

표에서 1로 이루어진 가장 큰 정사각형의 넓이를 구하는 문제입니다.

dp를 사용해서 풀 수 있습니다.

 

dp[i][j]는 (i, j)를 우하단 꼭짓점으로 하는 정사각형 중 가장 큰 정사각형 한 변의 길이입니다.

(i, j)의 값이 1일 경우에만 정사각형을 이룰 수 있습니다.

(i, j)의 값이 1일 경우, dp[i][j]의 값은 위쪽, 왼쪽, 좌상단의 셀 값 중 최솟값에 1을 더한 값입니다.

 

점화식은 아래와 같습니다.

• (i, j)가 0인 경우, dp[i][j] = 0
• (i, j)가 1인 경우, dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1

 

가장 큰 정사각형의 넓이를 구해야 하므로, 가장 큰 dp값의 제곱을 반환합니다.