[프로그래머스] Level2 - 가장 큰 정사각형 찾기(Javascript)

프로그래머스

▶ 문제 요약

1. 1과 0으로 채워진 표가 있다. 표 1칸은 1 * 1 정사각형으로 이루어져 있다. 

2. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 리턴해라. 

 

▶ 정답 코드

function solution(board) {
     let answer = 0;
     let column = board.length;
     let row = board[0].length;
     // board와 같은 2차원 배열 dp를 생성
     let dp = Array.from(Array(column), () => Array(row).fill(0));
     
     // 첫 번째 행의 dp값을 board의 값과 같게 맞춰준다. 
     for (let i = 0; i < column; i++) {
       	dp[i][0] = board[i][0];
        // 넓이의 최댓값 찾기
        answer = Math.max(answer, dp[i][0]);
     
     }
     
     // 첫 번째 열의 dp값을 board의 값과 같게 맞춰준다. 
	 for (let j = 0; j < row; j++) {
         dp[0][j] = board[0][j];
         answer = Math.max(answer, dp[0][j]);
     
     
     }
     
     // 두번째 행과 열부터 마지막 행과 열까지 순회하면서
     for (let i = 1; i < column; i++) {
         for (let j = 1; j < row; j++) {
             // 값이 1이라면
             if (board[i][j] === 1) {
                // (i, j) 위치에서 만들 수 있는 가장 큰 정사각형의 한 변의 길이는
                // 왼쪽 위, 위, 왼쪽 중에서 최솟값에서 +1을 더한다.
                dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) +1;
                answer = Math.max(answer, dp[i][j]);
             }
         }
     
     }
     // 가장 큰 정사각형의 한 변의 길이를 제곱 == 넓이
     return answer * answer;


}

▶ 풀이 과정

1. 각 위치에서 만들 수 있는 정사각형의 최대 크기를 저장해두면, 다른 위치에서의 정사각형의 크기를 계산하는데 재사용할 수 있다. 그래서 dp를 사용했다. 

 

2. 행과 열의 길이를 변수에 담고 나서 board와 똑같은 2차원 배열을 담아서 기본 값은 0으로 설정한다. 

 

3. 첫 번째 행과 첫 번째 열에서 만들 수 있는 정사각형의 크기가 그 자리의 값과 동일하다. 열의 경우에는 위쪽의 값이 존재하지 않고 행의 경우에는 왼쪽, 왼쪽 위의 값이 존재하지 않기 때문이다. 그래서 board와 똑같은 값을 dp에 저장하고 answer에는 dp 배열 중에 가장 큰 값을 저장한다. dp 배열의 값이 정사각형의 한 변의 길이를 나타내므로, dp 배열의 값 중 가장 큰 값이 가장 큰 정사각형의 한 변의 길이가 된다. 

 

4. 두 번째 행과 열부터 마지막 행과 열까지 순회하면서 dp를 계산하고 answer을 갱신한다. board[i][j]가 1이라면 (i, j) 위치에서 만들 수 있는 가장 큰 정사각형의 한 변의 길이는 왼쪽 위, 위, 왼쪽 중에서 가장 작은 값에 1을 더한 값이 된다. 

 

5. 한 변의 길이의 제곱한 것이 넓이다.