[C/C++] 백준 #1915 가장 큰 정사각형(동적 계획법)

이번 문제는 숫자가 써져있는 배열에서 1로만 채워진 가장 큰 정사각형을 찾으라는 문제입니다.

 

largest square

 

기본적인 알고리즘은 현재 셀을 포함한 가장 큰 정사각형을 찾는 것입니다.  현재 셀이 0이면 가장 큰 정사각형은 0입니다.  현재 셀이 1인 경우에만 가능하죠.

 

A					B
C					D

위의 그림에서 D에서 가장 큰 정사각형을 찾기 위해서는 D의 값이 0이면 0의 값이 됩니다.  D의 값이 1일때만, ABCD 구역에서 D를 포함한 가장 큰 정사각형의 넓이를 구하는 것이죠.

 

첫번째는 A에서 가장 큰 정사각형입니다.  이 경우에는 D와 대각선으로 이웃한 셀은 1로 설정이 되어 있지않다면 0의 값을 가집니다.

다음으로는 AB에서 가장 큰 정사각형입니다.  D의 위의 셀값은 1이 아니라면 0이겠죠.  다음으로는 AC에서 가장 큰 정사각형입니다.  역시  D의 왼쪽 셀은 1이겠죠.  이중 최소의 정사각형 크기를 가지고 있는 값을 찾습니다.  예를 들어서 A가 \(3^2\) 정사각형, B가  \(2^2\), C가 \(3^2\)이라면, B가 가장 적죠.  그러면 D를 포함할 경우 가장 큰 정사각형은 \( (2+1)^2 \)이 된다는 것이죠.

 

이렇게 구할 때마다 최대값을 보관하고 있으면, 결국 최대의 정사각형을 찾을 수가 있습니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//-----------------------------------------------------
//    baekjoon #1915
//        - by Aubrey Choi
//        - created at 2019-10-18
//-----------------------------------------------------
#include <stdio.h>

int main()
{
    int dp[1000][1000], min, max=0, n, m, i, j;
    char board[1000][1004];
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++) scanf("%s",board[i]);
    for(i=0;i<n;i++) if(board[i][0]=='1') dp[i][0]=1,max=1; else dp[i][0]=0;
    for(i=0;i<m;i++) if(board[0][i]=='1') dp[0][i]=1,max=1; else dp[0][i]=0;
    for(i=1;i<n;i++) for(j=1;j<m;j++)
    {
        if(board[i][j]=='0') { dp[i][j]=0; continue; }
        min = dp[i-1][j-1];
        if(min > dp[i-1][j]) min = dp[i-1][j];
        if(min > dp[i][j-1]) min = dp[i][j-1];
        dp[i][j] = min+1;
        if(min+1 > max) max=min+1;
    }
    printf("%d\n", max*max);
}