가장 큰 정사각형

문제 설명

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으로만 이루어져 있습니다.

고민

처음에 많은 생각을 하고 도전해서 코드를 짜봤지만, 내가 생각한 방법은 정답을 잘 구해낼 수 있을거라고 생각이 드는 코드는 없었다. 그래서 구글링을 통해서 문제의 접근 방법을 찾아냈다. 이 문제의 경우 정확도 + 효율성 테스트까지 있는데, 이를 해결하기 위해서는 동적프로그래밍을 사용해야 된다는 것을 알았다. 하지만, 어떻게 적용해야하는지 생각을 못해서 아예 다른 사람의 풀이 방식을 보고 코드를 구현했다.

풀이

1	2
1	1
1	1(현재 인덱스)

이 존재할 때, 현재 인덱스에서 가로로 -1, 세로로 -1, 가로&세로 -1 해준 값들 중에서 최솟값을 뽑아 그 값에서 +1을 하고, 이를 현재 인덱스의 값으로 바꿔준다. 그렇게 하면,

1	2
1	1
1	2

이러한 배열이 완성되는데, 위의 배열에서 2*2로 4가 되는 것을 알 수 있다.

2. 1번 방식으로 모든 배열을 조사하게 되면 가장 큰 값을 구하고 그 값을 제곱해주면 가장 큰 정사각형의 넓이를 얻을 수 있게 된다.
3. 여기서, 현재 인덱스가 1,1부터 시작해야 현재 인덱스에서 빼줄 수 있기 때문에 배열의 시작은 1,1부터 시작하면 된다.

완성 코드

function solution(board) {
  var answer = 1234;
  let maxPoint = 0;

  if (board.length < 2 || board[0].length < 2) {
    //둘 중에 하나라도 길이가 1이라면 가장 큰 정사각형은 넓이가 1이기 때문에 배열 안에 1이 있는지 조사한다.
    for (let i = 0; i < board.length; i++) {
      for (let j = 0; j < board.length; j++) {
        if (board[i][j] === 1) {
          //1이 존재한다면, 최대 넓이는 1*1이 된다.
          maxPoint = 1;
        }
      }
    }
  } else {
    for (let i = 1; i < board.length; i++) {
      for (let j = 1; j < board[i].length; j++) {
        if (board[i][j] === 1) {
          let minPoint = Math.min(
            board[i][j - 1],
            board[i - 1][j],
            board[i - 1][j - 1]
          );
          board[i][j] = minPoint + 1;
          if (board[i][j] > maxPoint) {
            maxPoint = board[i][j];
          }
        }
      }
    }
  }

  answer = maxPoint * maxPoint;

  return answer;
}

아쉬운 점 & 느낀 점

내 생각으로 푼 문제가 아니라 구글링을 통해서 푼 문제기 때문에 개운한 느낌은 아니다. 하지만, 아예 문제를 어떻게 풀어야하나 감도 잡히지 않은 상태였고, 역시나 사용된 알고리즘이 동적 프로그래밍이였는데, 이태까지 동적프로그래밍 문제는 풀어보지 않아서 어떻게 해야하는 감이 안잡히는 것이였다. 그래도 이번 기회에 동적 프로그래밍에 대해서 조금은 감이 잡혀서 그걸로 만족해야겠다.