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

https://programmers.co.kr/learn/courses/30/lessons/12905

프로그래머스

 

코드

class Solution
{
    public int solution(int [][]board)
    {
        int answer = 0;
        int[][] newBoard = new int[board.length+1][board[0].length+1];
        // 새로운 배열 생성
        for(int i=0; i<board.length; i++)
            for(int j=0; j<board[i].length; j++)
                newBoard[i+1][j+1] = board[i][j];
        
        int max = 0;
        
        // 만들 수 있는 정사각형 검사
        for(int i=1; i<newBoard.length; i++){
            for(int j=1; j<newBoard[i].length; j++){
                /* 2x2 사각형의 우측하단 꼭짓점을 기준으로 정사각형이 되는지 체크한다.
                 * 현재 값이 1인경우 좌←, 상↑, 좌상↖ 체크 
                 * ←, ↑, ↖ 값이 모두 1인경우 정사각형을 만들 수 있음
                */ 
                if(newBoard[i][j] == 1){
                    int left = newBoard[i-1][j];    // 좌측 값
                    int up = newBoard[i][j-1];      // 상단 값
                    int leftUp = newBoard[i-1][j-1];// 좌측상단(대각선) 값
                    int min = Math.min(left, Math.min(up, leftUp)); 
                    newBoard[i][j] = min+1;
                    max = Math.max(max, min+1);
                }
            }
        }
        answer = max * max;
        return answer;
    }
}

풀이

문제를 처음 보고 든 접근방식은 모든 가능한 정사각형의 크기를 찾아주는 식이었는데,

그럴경우 for문이 4개로 O(n^4)의 시간복잡도와 시간초과때문에 다른 방법을 생각해봤지만 떠오르진 않았다.

다른 사람들의 풀이를 참고하니 DP로 풀었다.

어떻게 ? 

2x2 크기의 정사각형을 기준으로 가능한 모든 정사각형을 검사하는데, 

배열의 탐색을 →↓우측으로, 하단으로 검사하기 때문에 우측하단의 꼭짓점을 기준으로 잡는다.

 

 

문제의 예제 입출력을 기준으로 보면 탐색은 위 색칠한 (1,1) 부터 시작한다.

(1,1)부터 시작해서 [좌측, 상단, 좌측 상단]의 값을 확인해가며 현재 값을 최솟값+1로 설정해준다.

왜 현재값을 최솟값+1로 설정하는지 보자.

현재 (1,1)을 기준으로

좌측(1,0) = 1

상단(0,1) = 1

좌측상단(0,0) = 0

이다. 그럼 정사각형을 만들 수 없으므로 현재 값을 최솟값+1 (0+1) = 1로 설정한다.

 

그럼 (1,2)를 보면 [좌측, 상단, 좌측 상단]의 값들이 전부 1이므로 현재값은 2로 변경이 된다.

배열의 끝까지 위 과정을 반복하면 아래와 같이 된다.

그럼 위 과정에서 가장 큰 정사각형의 크기는 현재 값(3)의 제곱이 된다.

 

하지만 위 과정에서 새로운 배열(newBoard)를 생성하고, 배열의 크기를 +1 더해준 것은 다음과 같은 경우가 생기기 때문인데,

행이 1이거나 열이 1인 배열의 경우, 예외가 발생한다.

위와 같이 행이 1이거나, 열이 1일경우 값이 1이 있으면 정사각형의 최대 크기는 1이다.

따라서 배열의 크기를 +1로 설정해줘서, 배열이 [0][n] 값과 [n][0]의 값을 모두 0으로 채워서 검색해야한다.

배열의 크기를 +1로 잡아서 설정해주면 아래와 같이 0행, 0열 기준으로 0값이 들어가기 때문에 예외를 처리해줄 수 있다.

 

비슷한 문제

백준 1051 숫자정사각형