[백준/C++] 1915번 가장 큰 정사각형

문제 링크

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

1915번: 가장 큰 정사각형

 

접근 방법

이 문제를 완전 탐색으로 풀려고 한다면 모든 칸을 접근하며 정사각형 형태인지를 판별해야할 것 입니다. 정사각형 형태인지 판별하는 것은 쉽지만 정사각형의 길이가 1 ~ min(n, m)인 경우까지 확인해보아야 하므로 정확한 계산은 어렵지만 못해도 n * m * min(n, m)의 수행 시간을 가질 것이라고 생각되고 이는 최악의 경우에 1초를 넘길 것입니다.

따라서 이전의 정사각형 크기를 기록하여(dp 배열을 이용한 메모이제이션) 현재 위치에서의 최대 정사각형의 크기를 빠르게 구할 수 있도록 고민해보았습니다. 배열을 map[i][j]로 표현했을 때 map[i][j]가 1이라면 정사각형의 크기는 1입니다.      dp[i][j]를 map[0][0]에서 시작하여 map[i][j]에서 끝나는 정사각형 크기라고 가정해봅시다.

이때 dp[i][j]는 dp[i - 1][j]  => (내 바로 위 쪽에서 있을 수 있는 최대 정사각형 크기) 

dp[i][j - 1] => (내 바로 왼쪽에서 있을 수 있는 최대 정사각형 크기)

dp[i - 1][j - 1] => (내 바로 왼쪽 위 대각선에서 있을 수 있는 최대 정사각형 크기)

이 세 값중 가장 작은 값에 1을 더한 것입니다.

위와 같은 배열이 주어져 있고 정의를 따라 dp 배열을 ?(4, 4) 위치 전까지 기록했다고 생각합시다. 이때 ?의 위치가 3이 될 수 없는 이유는 배열을 살펴보면 가장 왼쪽 아래가(4, 2) 0이기 때문입니다.

dp[3][4]와 dp[3][3] 위치에서는 크기가 2인 정사각형이 유지가 되지만 dp[4][3] 위치의 정사각형 크기가 2가 되지 않기 때문에 dp[4][4]는 셋 중 가장 작은 정사각형 크기에 의해 결정되는 것입니다.

다만 위와 같은 점화식은 배열의 현재 위치(map[i][j])가 1일 때만 실행해주어야합니다. map[i][j] 가 0이라면 우리가 세운   dp의 정의에 의해 map[i][j]에서 끝나는 정사각형 크기는 0이 되기 때문입니다.

위와 같이 기록된 dp를 이용하여 정사각형 크기를 빠르게 판별할 수 있다면 O(n * m) 시간안에 모든 칸에서 있을 수 있는 최대 정사각형의 크기를 구할 수 있으므로 시간 내에 통과될 수 있습니다.

코드

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int n, m, dp[1001][1001], answer;
vector<string> map;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        map.push_back(s);
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(map[i - 1][j - 1] == '1') dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
            else continue;
            answer = max(answer, dp[i][j]);
        }
    }
    cout << answer * answer;
}

 

코드 설명

현재 배열의 값이 1인 경우에만 현재 위치에서의 가장 큰 정사각형이 존재할 수 있으므로 문제의 접근 방법인 dp[i - 1][j] , dp[i][j - 1], dp[i - 1][j - 1] 중에서의 최소값 + 1을 하는 방식으로 dp 배열을 기록하였고 정답을 출력할 answer과 계속 비교하여 최신화 하였습니다.