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

문제

문제 : 가장 큰 정사각형 찾기

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

처음에는 첫번째 좌표부터 끝까지 하나하나 해보는 식으로 했지만 효율성에서 탈락했다.
계속해서 조건을 추가해 시간을 단축 시켰지만 결국 실패했다.

계속 고민을 해도 해결을 못해서 인터넷에서 풀이를 배워서 해결했다.

Dynamic programming을 이용해서 해결해야 됐다.

해결방법

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

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

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

말 또는 코드로 이해가 안된다면 한번 그려보면 이해가 수월하다.

• 파란색줄은 고정이다. (비교를 해줘야 되기 때문)
• 3 좌표와 비교해가면서 가장 작은점+1을 넣어주면된다.
• 주변이 모두 클 경우 그 주변은 그 크기만큼의 정사각형 3개로 이루어진 것이기 때문에 그 크기보다 +1크기의 정사각형이 가능하다.

---

코드

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

---

아직 알고리즘 문제를 많이 풀어보지 못한 탓에 다이나믹 프로그래밍(DP)으로 해결한 적이 이번 처음이다. 처음이지만 이런 규칙을 이용해서 시간을 크게 단축시키는 코드를 보고 놀라웠고 계속 연습해야 겠다고 생각한다.