[BOJ] 1915 : 가장 큰 정사각형

문제 링크

1915번: 가장 큰 정사각형 (acmicpc.net)

1915번: 가장 큰 정사각형

0,1로 이루어진 배열에서 1로된 가장 큰 정사각형의 크기를 구하는 문제.

https://jk6722.tistory.com/entry/BOJ-1028-%EB%8B%A4%EC%9D%B4%EC%95%84%EB%AA%AC%EB%93%9C-%EA%B4%91%EC%82%B0

[BOJ] 1028 : 다이아몬드 광산

저번에 풀어봤던 다이아몬드 광산의 하위버전인 것 같다.

풀이

먼저 각 지점마다 그 지점부터 가로로 최대길이를 Right 라는 배열에 저장해두었다.

만약 그림처럼 맨 위쪽, 맨 왼쪽 지점인 (1,1)을 기준으로 최대길이가 아래로 가면서 각각 3, 2, 2 이다. 이때 최대 사각형으 크기는 4인 것을 알 수 있다. 그림으로 봐서 3, 2, 2일 때 최대크기가 4인 것을 바로 알 수 있지만 코드로는 어떻게 작서할까?

(1,1) 지점을 시작으로 x축은 고정해둔채 y만 하나씩 늘려가면서 탐색한다. 여기서 탐색 범위는 유동적으로 바꿔줘야한다. 저 그림을 예시로 처음에 (1,1) 지점에서 가로 최대길이는 3이므로 3X3 짜리 정사각형을 만들 수 있다는 가능성을 열어둔다. 하지만 (2,1)로 내려왔을 때 가로 최대길이가 2이므로 3X3 짜리 정사각형은 이미 불가능하다. 그리고 현재까지 최대 크기는 4이고 더 이상 탐색은 의미가 없다. 탐색범위를 줄여서 탐색을 종료시킨다.

(i, j) 지점에서 최대 정사각형 크기를 탐색한다고 가정했을 때 탐색 코드는 아래와 같다.

			int boundary = Right[i][j];
			int Max = 1;
			for (int k = 0; k < boundary; k++) {
				if(Right[i+k][j] >= k + 1)
					Max = max(Max, k + 1);
				boundary = min(boundary, Right[i + k][j]);
			}
			ans = max(Max, ans);

boundary는 가능성을 열어둘 수 있는 정사각형 한 변의 길이의 최대이다. 초기값은 시작 지점의 최대 가로 길이이다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef priority_queue<pair<pair<ll, int>, pair<int, int>>, vector<pair<pair<ll, int>, pair<int, int>>>, greater<pair<pair<ll, int>, pair<int, int>>>> Priority_queue;
const long long INF = LLONG_MAX;
const int MAX_N = 1000 + 5;
int Map[MAX_N][MAX_N];
int N, M;
int Right[MAX_N][MAX_N];
 
int main(void) {
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%1d", &Map[i][j]);
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (Map[i][j] != 1)
                continue;
            if (j > 0 && Right[i][j - 1] != 0) {
                Right[i][j] = Right[i][j - 1] - 1;
                continue;
            }
            int cnt = 0;
            for (int k = j; k < M; k++) {
                if (!Map[i][k])
                    break;
                cnt++;
            }
            Right[i][j] = cnt;
        }
    }
    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!Map[i][j])
                continue;
            int boundary = Right[i][j];
            int Max = 1;
            for (int k = 0; k < boundary; k++) {
                if(Right[i+k][j] >= k + 1)
                    Max = max(Max, k + 1);
                boundary = min(boundary, Right[i + k][j]);
            }
            ans = max(Max, ans);
        }
    }
    cout << ans * ans << "\n";
 
    return 0;
}
 

ans에 저장된 값은 만들 수 있는 가장 큰 정사각형의 한 변의 길이 이므로 크기는 ans * ans 를 출력해주어야 한다.

2년 전에 못풀었던 문제를 풀었다.