[Javascript/자바스크립트] (프로그래머스) 가장 큰 정사각형 찾기

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

코드

function solution(board) {
  let answer = 0;

  const r = board.length;
  const c = board[0].length;
  const acc = Array.from(new Array(r + 1), () => new Array(c + 1).fill(0));

  for (let i = 1; i <= r; i++) {
    for (let j = 1; j <= c; j++) {
      if (board[i - 1][j - 1] === 1) {
        acc[i][j] =
          Math.min(acc[i - 1][j], acc[i][j - 1], acc[i - 1][j - 1]) + 1;
        answer = Math.max(answer, acc[i][j] ** 2);
      }
    }
  }

  return answer;
}

 

누적합을 사용하면 효율적으로 풀 수 있는 문제다.

 

아래 그림을 보면 어떻게 누적합으로 푼다는건지 좀 더 쉽게 이해할 수 있다.

그림에서 빨간 칸이 현재 위치라고 할 때, 현재 위치에서 가능한 최대 정사각형의 크기는 왼쪽, 위쪽, 그리고 대각선 왼쪽 위의 세 위치에서 가능한 최대 정사각형 크기의 최소값에 1을 더한 값이 된다. 이렇게 최소값을 사용하는 이유는 다음과 같다.

 

• 정사각형은 네 변의 길이가 모두 같아야 함
• 세 방향 중 하나라도 작은 값이 있으면, 그 값이 제한요소가 됨
• 예: 왼쪽=2, 위쪽=3, 대각선=1 이면, 현재 위치에선 최대 2x2 정사각형만 가능

여기서 인접한 세 방향의 칸들에는 이미 반복문을 돌면서 구한 최대 정사각형의 크기가 저장되어 있기 때문에 이 세 값 중 최소값을 구하고 1을 더하면 현재 위치에서 가능한 최대 정사각형의 크기가 되는 것이다.