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

문제 링크

1️⃣ 문제 설명

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를 반환해 주면 됩니다.

---

2️⃣ 제한 사항

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

---

3️⃣ 입출력 예

4️⃣ 나의 풀이

function solution(board) {
  let answer = 0;
  const row = board.length;
  const 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) {
        const up = board[i - 1][j];
        const left = board[i][j - 1];
        const cross = board[i - 1][j - 1];
        const minNum = Math.min(up, left, cross);
        board[i][j] = minNum + 1;
        answer = Math.max(answer, board[i][j]);
      }
    }
  }

  return answer * answer;
}

0과1로 이루어진 board에서 변수에 담긴 2차원 배열 중 1로 이뤄진 가장 큰 정사각형을 찾는 문제

DP 활용

1. board[i][j]에 좌표에서 왼쪽위로 만들 수 있는 가장 큰 정사각형의 변의 길이를 저장한다.
2. 좌표의 위쪽, 왼쪽, 대각선 왼쪽 위 총 이렇게 3점을 비교해 결정한다.
3. board의 첫번째 column, row는 처음 비교대상의 기준으로 해야되기 때문에 남겨둔다.

   • board[i][j]가 0이 아닌 경우 정사각형 크기를 저장
   • board[i][j]에 위에서 말한 3좌표중 가장 크기가 작은 좌표+1을 저장

각 좌표에 자신의 정사각형 변의 길이가 저장 돼있기 때문에 3개 좌표 중 작은 것 하나가 껴있으면 작은 좌표 주변에 다른 큰 좌표의 길이만큼 범위 안에 0 이 있다는 의미이다.

• 흰색 == 고정
• 3 좌표와 비교하면서 가장 작은점 +1
• 주변이 모두 클 경우 그 크기만큼 정사각형 3개로 이뤄졌기 때문에 그 크기보다 +1의 정사각형 가능