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

 

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;
}

초기화:

  • answer: 가장 큰 정사각형의 한 변의 길이를 저장.

  • row: board의 행 수.

  • column: board의 열 수.

  • 만약 row 또는 column이 1 이하인 경우, 정사각형의 최대 크기는 1이므로 1을 반환.

 

동적 프로그래밍 적용:

  • 이중 for 루프를 사용하여 board의 각 셀을 순회.

  • 각 셀 (i, j)에서 board[i][j]가 1인 경우, 왼쪽(board[i][j-1]), 위(board[i-1][j]), 왼쪽 대각선(board[i-1][j-1]) 값을 확인하여 최소값에 1을 더한 값을 board[i][j]에 저장.

  • answer를 현재 board[i][j]와 비교하여 최대값으로 업데이트.

 

결과 반환:

  • 가장 큰 정사각형의 한 변의 길이를 제곱하여 넓이를 반환.

 

동작 예시:

  • board 배열이 주어졌을 때, 가장 큰 정사각형의 넓이를 계산하여 반환합니다.

1 1 1 1
1 1 1 1
1 1 1 1

결과는 9 (3x3 정사각형)입니다.