가장 큰 정사각형

가장 단순하게 생각해 볼 수 있는 방법은 특정 좌표가 1이라면, 가능한 정사각형들을 반복문을 돌면서 하나씩 탐색해보는 방법이다.

이해를 돕기 위해 함수로 표현하면 다음과 같다.

//size : 정사각형의 변의 길이
bool IsPossible(int row, int col, int size)
{
	for(int i = row; i < row + size; i++){
    		for(int j = col; j < col + size; j++){
              	if(board[i][j] == 0){
                  	return false;
              	}
        }
    }
    return true;
}

그러나 이 방법으로는 효율성 부분을 통과할 수 없었다.

 

두 번째 방법으로 가장 큰 정사각형을 찾는게 답이기 때문에 지금까지 계산했었던 가장 큰 변의 길이로 계산하는 방법이었다. 그러나 이것도 효율성에서 실패했었다.

 

세 번째 방법은 DP의 개념을 응용해야 하는데, 길이가 W인 정사각형을 만드는데에 W - 1인 정사각형을 만드는 경우가 부분문제로 포함된다. 

//사각형의 오른쪽 하단 기준, 좌표 (i, j)를 포함하여 만들 수 있는 가장 큰 정사각형의 길이
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])

 

이해를 돕기 위해, 길이가 3인 정사각형을 DP방식으로 구해보면 테이블은 다음과 같다.

1	1	1
1	2	2
1	2	3

길이가 2인 정사각형은 사각형의 오른쪽 하단 값 1을 기준으로 위쪽, 왼쪽, 왼쪽 대각선이 모두 1이여야 한다.

마찬가지로 길이가 3인 정사각형은 오른쪽 하단 값 1을 기준으로 위쪽, 왼쪽, 왼쪽 대각선이 모두 1이여야 하는데, 앞에서 미리 구해놓은 길이 2인 정사각형의 값을 이용하는 것이다!

정답코드

#include <iostream>
#include<vector>
#include <algorithm>
using namespace std;
#define MAX_SIZE 1000
int width, height;

int solution(vector<vector<int>> board)
{
    int answer = 0;
    int MaxSize = 0;
    //dp[W][H] = 오른쪽 하단 기준, 가장 큰 정사각형의 변의 길이
    height = board.size();
    width = board[0].size();
    if(height == 1 || width == 1)
        return 1;
    for(int i = 1; i < height; i++){
        for(int j = 1; j < width; j++){
            if(board[i][j] == 1){
                board[i][j] = min(board[i - 1][j - 1], 
                              min(board[i][j - 1], board[i - 1][j])) + 1;
                MaxSize = max(MaxSize, board[i][j]);
            }
        }
    }
    answer = MaxSize * MaxSize;
    return answer;
}