[BOJ 1915 // C++] 가장 큰 정사각형

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1915번 문제인 가장 큰 정사각형이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

이 문제에는 각 칸에 "이 칸을 오른쪽 아래 끝으로 갖는 최대 정사각형의 크기"를 찾아나가는 것을 DP를 이용하여 빠르게 계산해 간단히 풀 수 있다.

 

지금 살펴보고 있는 칸이 오른쪽 아래 꼭짓점인 정사각형의 최대 크기는 바로 윗칸, 왼쪽칸, 왼쪽위칸 세 곳으로 각각 끝나는 최대 정사각형의 크기의 최댓값들 가운데 최솟값 +1을 해준 값이라는 관계가 있다는 것을 관찰할 수 있기 때문이다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <cmath>
using std::cin; using std::cout;
using std::string;
using std::min;

string board[1001];
int square[1001][1001];

int main()
{
    int row, column; cin >> row >> column;
    for (int i = 0;i <= column;i++) {
        board[0] += '0';
    }
    string temp;
    for (int i = 1;i <= row;i++) {
        cin >> temp;
        board[i] = '0';
        board[i] += temp;
    }
    int ans = 0;
    for (int i = 1;i <= row;i++) {
        for (int j = 1;j <= column;j++) {
            if (board[i][j] == '1') {
                square[i][j] = min(square[i - 1][j - 1], min(square[i - 1][j], square[i][j - 1])) + 1;
                if (square[i][j] > ans) ans = square[i][j];
            }
        }
    }
    cout << ans*ans;
}