가장 큰 정사각형 찾기

문제

문제 설명

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

예를 들어

1	2	3	4
0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 있다면 가장 큰 정사각형은

1	2	3	4
0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

제한사항

• 표(board)는 2차원 배열로 주어집니다.
• 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
• 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
• 표(board)의 값은 1또는 0으로만 이루어져 있습니다.

---

입출력 예

board	answer
[[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]	9
[[0,0,1,1],[1,1,1,1]]	4

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.

입출력 예 #2
| 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
로 가장 큰 정사각형의 넓이는 4가 되므로 4를 return합니다.

 

접근 및 풀이

값이 1인 연속된 열의 수를 누적 시키면서 최대 수보다 크면 해당 열의 아래가 정사각형인지 알아보려 했으나 열의 아래 중간에 0이 끼어있는 작은 정사각형을 가려낼 수 없어서 실패했다. 풀이를 보니 보드의 수를 바꿔가며 푸는 방법이 있었다.

코드

function solution(board) {
  const rowLen = board.length;
  const colLen = board[0].length;
  let max = 0;
  if (colLen < 2 || rowLen < 2) {
    if (board.toString().match(/1/) === null){
      return 0;
    } else {
      return 1;
    }
  }
  for (let col = 0; col < colLen - 1; col++) {
    for (let row = 0; row < rowLen - 1; row++) {
      if (board[row][col] > 0) {
        max = max === 0 ? 1 : max;
        if (board[row][col + 1] > 0
          && board[row + 1][col] > 0 
          && board[row + 1][col + 1] > 0) {
          const min = Math.min(board[row][col]
            ,board[row][col + 1]
            ,board[row + 1][col]);
          
          board[row + 1][col + 1] = min + 1;
          if (max < (min + 1)) max = min + 1;
        }
      }
    }
  }
  return max*max;
}

출처

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