<Level 2> 가장 큰 정사각형 찾기 with JS

 

문제 설명

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

예를 들어

 

0	1	1	1
1	1	1	1
1	1	1	1
0	0	1	0

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

 

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

function solution(board) {
  let answer = 0;
  if (board.length === 1) return Math.max(...board[0]);
  for (let i = 1; i < board.length; i++) { // 행 탐색
    answer = Math.max(answer, board[i][0]);
    for (let j = 1; j < board[0].length; j++) { // 행 내 열 탐색
      if (board[i][j] === 0) continue;
      board[i][j] = Math.min(board[i - 1][j - 1], board[i - 1][j], board[i][j - 1]) + 1;
      answer = Math.max(answer, board[i][j]);
    }
  }
  return answer ** 2;
}

 

 - dp로 풀면 좋겠다고 생각하고 접근한 문제이다.

 

 - 처음에는 그래프를 탐색하며 자신의 바로 오른쪽, 바로 아래, 오른쪽대각선 아래를 탐색하여 모두 1 이상이면 더하거나 하는 방식으로 접근했다. 하지만 도저히 풀리지 않아서 거꾸로 생각해보았다. dp문제는 종종 답이 어떤식으로 도출되면 좋을지를 먼저 생각하면 풀리곤 한다.

 

0	1	1	1
1	1	1	1
1	1	1	3
0	0	1	0

 

 - 답이 위처럼 해당하는 곳에 3이라고 표현하는 것이 목표로 점화식을 짜게되니 금방 답이 풀렸다. 위와 같이 답이 도출되게 만드려면 오른쪽이 아니라 왼쪽을 확인해야했다. 즉 바로 왼쪽, 바로 위쪽, 왼쪽대각선 위를 탐색하여 값이 0이 아닌지를 확인하는 방향으로 가야 한다.

 

 - 그런식으로 dp 그래프를 구현하면 아래와 같이 표현된다.

 

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

 

 

 - 점화식은 다음과 같다.

  dp[x][y] = min(dp[x-1][y-1], dp[x-1][y], dp[x][y-1]) + 1  

 

 - 세 개의 값을 탐색하고 그 중 가장 작은 값보다 1 크도록 만들었다. 현재 값이 1일 경우만 체크하므로 세 가지 값중 하나가 0 이더라도 1은 유지된다.

 

 - 반복마다 answer과 현재 값 중 큰 값을 answer에 새로 저장한다.

 

 - 0행이 아닌 1행부터 탐색해야하므로 행의 길이가 1인 경우 가장 먼저 예외처리를 하였다. 이는 그냥 가장 큰 값을 리턴하도록 하면 된다. (0 or 1) 그리고 0열의 경우 세 가지 값을 확인할 수 없으므로 따로 먼저 처리하도록 한 후 j는 1부터 시작하도록 하였다.

 

 

---

 

참고

 

코딩테스트 연습 - 가장 큰 정사각형 찾기