백준 1915: 가장 큰 정사각형

https://www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

문제는 다음과 같습니다.

 

정해

제가 실제로 푼 방법이랑은 다르지만, dp[i][j]=((i, j)를 포함하는 1로만 된 정사각형의 한 변의 최대 길이)라 잡으면 풀린다고 합니다. 이 방법은 다른 블로그에 많이 소개되어있으니 생략하겠습니다.

풀이

제 풀이입니다.

일단 1-based로 입력을 받습니다. 그리고 (1,1)부터 (i,j)까지의 모든 수의 합을 나타내는 배열 s[i][j]를 구합니다.(포함과 배제의 느낌으로)

만일 모든 수가 0이라면, 0을 출력하고 프로그램을 종료합니다.

1이 한 개 이상 있다면, (i,j)부터 시작하는 한 변의 길이가 k인 정사각형이 과연 1로 꽉 차있는지 탐색합니다(아래 코드에서는 k를 (정사각형의 한 변의 길이)-1로 두고 풀었습니다). 만일 그 정사각형이 1로 꽉 차있다면 정사각형 안의 모든 수의 합은 k²가 되겠죠. 결국 정사각형 안의 모든 수를 앞서 구한 구간 합으로 계산해서 k²과 같은지 확인하면 됩니다.

 

코드

위의 풀이로 짠 코드입니다.

#include <bits/stdc++.h>
using namespace std;
string b; //입력을 위한 문자열
int a[1001][1001], s[1001][1001]; //배열과 구간합
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    bool x=0;
    cin >> n >> m;
    for(int i=1; i<=n; i++) {
        cin >> b;
        for(int j=1; j<=m; j++) {
            a[i][j]=(int)b[j-1]-48;
            x=x|a[i][j]; //a[i][j]가 모두 0이라면 x값은 끝까지 0임
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]; //구간합 구하기
        }
    }
    if(!x) {cout << 0; return 0;} //x가 0이라면 0 출력 후 종료
    int c=0; //(최대 정사각형 한 변 길이)-1
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            for(int k=c+1; k<=min(n-i, m-j); k++) { //k가 c 이하이면 계산할 필요 없음
                if(s[i+k][j+k]-s[i-1][j+k]-s[i+k][j-1]+s[i-1][j-1]==(k+1)*(k+1)) c=k; //(i,j)부터 (i+k, j+k)의 합이 정사각형의 넓이인지 확인
            }
        }
    }
    c++; //c에다 1을 더하여 c를 최대 정사각형의 한 변의 길이로 만듦
    cout << c*c;
}

 

감사합니다.