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

金弘均·2021년 9월 16일
0

Baekjoon Online Judge

목록 보기
175/228
post-thumbnail

# Appreciation

/*
 * Problem :: 1915 / 가장 큰 정사각형
 *
 * Kind :: Dynamic Programming
 *
 * Insight
 * - (i,j) 를 맨 왼쪽 위 꼭지점으로 하는 변의 길이가 r 인 정사각형인지 판단할 때,
 *   그 정사각형에 포함된 모든 칸들이 1 인지 확인한다면... 시간초과를 받을 수 밖에 없다
 *   + N=1000, M=1000, r=500 만 되더라도
 *     O(1000*1000*500*500) > O(10^8)
 *     # 좀더 효율적으로 정사각형을 판단할 수 있는 방법이 없을까?
 *       근처에 정사각형으로 판단된 정보가 있으면 이를 활용할 수 있을까?

 *
 * - 입력
 *   0 0 0 1
 *   0 0 1 1
 *   0 0 1 1
 *   + dp
 *     0 0 0 1
 *     0 0 1 1
 *     0 0 1 2
 *     # 정사각형에서 (i,j) 를 맨 오른쪽 아래 꼭지점이라고 할 때,
 *       그러한 정사각형들 중 변의 최대 길이는
 *       (i-1,j) 를 맨 오른쪽 아래 꼭짓점으로 한 정사각형 중 변의 최대 길이와
 *       (i,j-1) 을 맨 오른쪽 아래 꼭짓점으로 한 정사각형 중 변의 최대 길이와
 *       (i-1,j-1) 을 맨 오른쪽 아래 꼭짓점으로 한 정사각형 중 변의 최대 길이의
 *       최솟값에 1 을 더한 값이다.
 *       ->  dp[i][j] = (i,j) 를 맨 오른쪽 아래 꼭지점으로 하는 정사각형 중 변의 최대 길이
 *           dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1
 *
 * Point
 * - dp[2][2] = 2 이라면
 *   각 (1,1) ~ (2,2) 칸이 1 로 이루어졌다는 것을 의미한다
 *   + 즉, dp[i][j] = r 이라면
 *     각 (i-(r-1),j-(r-1)), (i,j) 칸이 1로 이루어졌다는 것을 의미한다
 *     # dp[i][j] = r 이 되기 위해서는
 *       board[i][j] = 1 이며
 *       dp[i-1][j] >= r-1, dp[i][j-1] >= r-1, dp[i-1][j-1] >= r-1 이 되어야 한다
 *       -> 가능한 r 의 값을 for 문으로 일일이 검사하기 보다는 min 을 사용해서 빠르게 찾아주자
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N, M;
    cin >> N >> M;
    int board[N+1][M+1];
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=M; j++) {
            char c; cin >> c;
            board[i][j] = c - '0';
        }
    }

    // Process
    int dp[N+1][M+1]; /* dp[i][j] = (i,j) 를 맨 오른쪽 아래 꼭짓점으로 하는
                       *            정사각형 중 변의 최대 길이 */
    memset(dp, 0, sizeof(dp));
    int ans = 0; /* 가장 큰 정사각형의 넓이 */
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=M; j++) {
            if (board[i][j] == 1) { /* (i,j) 를 맨 오른쪽 아래 꼭짓점으로 하는 정사각형 */
                /* dp[i][j] = r
                 * if board[i][j] = 1
                 *    && dp[i-1][j] >= r-1
                 *    && dp[i][j-1] >= r-1
                 *    && dp[i-1][j-1] >= r-1 */
                dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
                ans = max(ans, dp[i][j]*dp[i][j]); /* 가장 큰 정사각형의 넓이 갱신 */
            }
        }
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글