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

가장 큰 정사각형 찾기

문제 설명

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

 

예를 들어

프로그래머스 - 표 설명 1

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

프로그래머스 - 표 설명 2

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

제한사항

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

입출력 예

board	answer
[[0,1,1,1], [1,1,1,1], [1,1,1,1], [0,0,1,0]]	9
[[0,0,1,1], [1,1,1,1]]	4

입출력 예 설명

입출력 예 #1

위의 예시와 같습니다.

 

입출력 예 #2

프로그래머스 - 표 설명 3

로 가장 큰 정사각형의 넓이는 4가 되므로 4를 return합니다.

코드

function solution(board)
{
    let answer = 0;
    let row = board.length;
    let col = board[0].length;
    
    // 행 또는 열이 1이면 정사각형의 넓이를 1로 반환.
    if(row < 2 || col < 2) return 1;
    
    // 그 외의 경우엔 루프를 돌며 계산을 수행
    for(let i = 1; i < row; i++) {
        for(let j = 1; j < col; j++) {
            // 만약 자신의 위치(현재 인덱스)의 값이 1이상일 경우
            if(board[i][j] !== 0) {
            	// 왼쪽상단(↖︎), 위쪽(↑), 왼쪽(←)의 최솟값을 구한 후 
                let min = Math.min(
                    board[i-1][j-1], 
                    board[i-1][j], 
                    board[i][j-1]
                );
                // 자신의 위치에 최솟값 + 1을 할당한다.
                board[i][j] = min + 1;
            }
            // 할당한 값의 최댓값을 answer에 할당해주고
            if(answer < board[i][j]) answer = board[i][j];
        }
    }
    // 정사각형의 넓이를 구한다.
    return answer * answer;
}

문제 이해와 풀이

문제를 보고 순간 멍해졌다. 아무리 봐도 답이 안나와서 결국 다른 사람의 풀이를 보고 풀게 되었다. 그 중 Wanna be 컴잘알님의 블로그 글이 가장 도움이 되었다. 해당 문제의 규칙은 다음과 같다. 

1. 만약 행 또는 열이 1이면 정사각형의 넓이는 1이다.
2. 루프를 돌며 만약 자신의 위치(현재 인덱스)의 값이 1이상일 경우 왼쪽상단(↖︎), 위쪽(↑), 왼쪽(←)의 최솟값을 구한 후 자신의 위치에 최솟값 + 1을 할당한다.
3. 2번 값의 최댓값을 answer에 할당해주고 정사각형의 넓이를 구한다.

각각을 비교해 그 중 최솟값을 구해 해당 인덱스에 1을 더해준다. (비교를 위해 board[1][1]번째부터 비교를 시작한다.)

정사각형의 넓이는 한 변의 길이 × 한 변의 길이이다. 즉 2번의 최솟값 + 1을 할당 해준다는 것은 한 변의 길이가 1씩 더해지는 것과 같다.

따라서 한 변의 길이의 최댓값에 제곱을 해주면 가장 큰 정사각형을 구할 수 있다.

---

이 문제를 풀고 이해하는데 이틀이라는 시간이 걸렸다. 물론 온전히 이틀을 투자한건 아니지만 처음엔 가볍게 시작했다가 '다이나믹 프로그래밍이 뭐지?'부터 시작해서 피보나치 수열, 클로저, 메모이제이션, 밑에서부터 계산하기, 동적 계획법이 도움이 되는 경우 등 역시 공부는 끝이 없다. 그래도 역시나 처음엔 내가 바보 같다가도 결국 시간이 지나면(계속 보다 보면) 조금씩 이해가 되기 시작한다. 이젠 이 루프가 어느정도 익숙해져서 스스로 위축은 되지 않으려 한다.