배열에서 가장 큰 정사각형 찾기

프로그래머스에서 제공하는 문제 중 하나입니다.

배열 내부를 탐색하여 가장 큰 정사각형을 찾는 알고리즘입니다.

배열은 아래와 그림과 같이 제공되며 1이 정사각형일 때, 배열 내부의 가장 큰 정사각형의 값을 return 합니다.

위와같은 배열이 있으며, 가장 큰 정사각형은 아래와 같습니다.

가장 큰 정사각형이 9칸을 차지하고 있으므로 답은 9입니다.



구현하는 방법이야 여러가지가 있겠지만 10000*10000의 배열이면 성능에 문제가 생기게 됩니다. 

그래서 성능을 고려하여 DP(Dynamic Programming)를 사용하여 구현할 수 있습니다.
자바스크립트로 구현한 방법은 아래와 같습니다.

function solution(board)
{
    var answer = 0;

    var lengthY = board.length;
    var lengthX = board[0].length;
    var max = 0;

    // 행이나 열의 길이가 2 미만이라면 직접 돌리면서 1이 하나라도 있는지 체크 합니다.
    // 하나라도 있으면 통과.
    if (lengthY < 2 || lengthY < 2) {
        for(var i = 0 ; i < lengthY ; i++){
            for(var j = 0;  j < lengthX ; j++) {
                if (board[i][j] === 1) {
                    max = 1;
                }
            }
        }
    } else {
        //아래 설명 참조
        for(var i = 1 ; i < lengthY ; i++){
            for(var j = 1;  j < lengthX ; j++) {
                if(board[i][j] === 1 ){
                    board[i][j] = Math.min(board[i - 1][j], board[i][j - 1], board[i - 1][j - 1]) + 1;
                    if (board[i][j] > max) {
                        max = board[i][j];
                    }
                }
            }
        }
    }

    return Math.pow(max, 2);
}

그럼 정사각형을 어떻게 찾는지 간단하게 설명하자면

  1. 배열의 [1][1]부터 반복문을 돌린다. (첫 번째 행, 첫 번째 열 무시, 이유는 2번 참고)
  2. 현재 값이 1일 경우, 좌측값, 상단값, 좌측상단값 중 가장 작은 값의 +1 한 값을 현재 값으로 할당.
  3. 배열이 끝날 때 까지 반복.
  4. 배열의 가장 큰 값이 현재 배열의 가장 큰 정사각형의 값이 된다.

아래에 그림을 참고하여 어떻게 돌아가는지 봅시다.


위 알고리즘을 돌리면 배열은 아래와 같이 바뀝니다.

값을 할당하면 위와같은 결과가 나옵니다.

저렇게 바꾸는 부분에대한 주석을 추가했습니다.

// 첫 번째 행열을 제외시키기 위해서 i와 j에 1을 할당합니다.
for(var i = 1 ; i < lengthY ; i++){
    for(var j = 1;  j < lengthX ; j++) {

        // 1이 아닐 경우 패스! 1인 값만 동적으로 변경해 줍니다.
        if(board[i][j] === 1 ){
            // 현재 값의 좌측값, 상단값, 좌측상단값 중 최소값에 +1을 해줍니다.
            board[i][j] = Math.min(board[i - 1][j], board[i][j - 1], board[i - 1][j - 1]) + 1;

            // 다시 배열을 돌리는 수고를 하지않기 위해서 max값을 찾아 저장해 줍니다.
            if (board[i][j] > max) {
                max = board[i][j];
            }
        }
    }
}

가장 큰 3의 제곱을 한 값이 정사각형의 크기이기 때문에 저장한 max 값을 아래와 같이 처리해줍니다.

    Math.pow(max, 2);

마치며

그림이 허접해서 죄송합니다.. :(

저작자표시