가장 큰 정사각형 찾기

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

가장 큰 정사각형 찾기Lv.2

12905

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

해설

2차원 배열 board 내에서 가장 큰 정사각형의 넓이를 찾는 문제를 풀기 위한 것입니다. board의 각 항목은 1 또는 0으로, 1은 해당 위치에 정사각형의 한 부분이 있는 것을 나타냅니다.

  • Name
    board 크기 확인
    Type
    Description

    행(row)과 열(column)의 크기를 확인합니다. 만약 행 또는 열의 크기가 1 이하인 경우에는 가장 큰 정사각형의 크기는 1이 될 수 밖에 없으므로 1을 반환합니다.

  • Name
    board 탐색
    Type
    Description

    각 위치에서 위(up), 왼쪽(left), 왼쪽 위 대각선(cross) 위치의 값을 확인합니다. 이 위치들이 모두 1인 경우에만 현재 위치에서 만들어질 수 있는 정사각형의 크기가 증가합니다.

  • Name
    정사각형의 크기 갱신
    Type
    Description

    위, 왼쪽, 왼쪽 위 대각선 위치 중 가장 작은 값(minNum)에 1을 더하여 현재 위치의 값을 갱신합니다. 이렇게 함으로써 현재 위치에서 만들어질 수 있는 가장 큰 정사각형의 크기를 저장하게 됩니다.

  • Name
    가장 큰 정사각형의 크기 확인
    Type
    Description

    만들어질 수 있는 가장 큰 정사각형의 한 변의 길이(answer)를 갱신합니다.

  • Name
    결과 반환
    Type
    Description

    가장 큰 정사각형의 넓이를 반환하기 위해 가장 큰 한 변의 길이(answer)를 제곱하여 반환합니다.

가장 큰 정사각형 찾기

function solution(board) {
  let answer = 0;
  let row = board.length;
  let column = board[0].length;

  if (row <= 1 || column <= 1) {
    return 1;
  }

  for (let i = 1; i < row; i++) {
    for (let j = 1; j < column; j++) {
      if (board[i][j] > 0) {
        let up = board[i - 1][j];
        let left = board[i][j - 1];
        let cross = board[i - 1][j - 1];
        let minNum = Math.min(up, left, cross);
        board[i][j] = minNum + 1;
        answer = Math.max(answer, board[i][j]);
      }
    }
  }
  return answer * answer;
}