[백준] 가장 큰 정사각형 1915번 (c++)

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

1915번: 가장 큰 정사각형

풀이 방법

dp 문제이다 문제를 쪼개는 방법이 중요하다.

쪼갤 때 사각형의 가장 왼쪽 위 배열을 기준으로 그 정사각형의 한 변의 길이를 기록한다.

가장 큰 정사각형의 변의 길이를 제곱하여 넓이를 구한다.

0000

1111

1111

0000

예를 들어 위 경우에서 왼쪽 위 모서리의 배열에 길이를 저장이면 dp[1][0] = 2, dp[1][1] = 2.. 이렇게 되지만

dp[2][0] 은 1이 된다 변의 길이가 2인 정사각형에 포함은 되지만 그 정사각형에서 왼쪽 위의 점이 아니기 때문이다

이렇게 문제를 쪼개면 [i][j]의 정사각형의 변의 길이는 [i+1][j], [i][j+1], [i+1][j+1]의 변의 길이중 가장 작은 것에다가 +1 을 한 것이 된다.( 겹치는 부분 때문에 그림 그려보면 이해 가능) 

그리고 기저 조건으로 i == n-1 or j == m-1 이 되면 그 보드의 값을 리턴하면 기저 조건까지 준비가 다 된다.(기저 조건을 확인 잘 못해서 시간을 좀 썼다)

bord 값이 1이면 재귀 호출을 해주고 0이면 return 0;을 해주면 된다.

#include <iostream>
#include <algorithm>
#include <memory.h> 
#include <vector>

using namespace std;

int n, m;
int dp[1001][1001];
int ans = 0;
int count(vector<vector<int>>& bord, int i, int j) {    
    if (i == n-1 || j == m-1) {        
        ans = max(ans, bord[i][j]);
        return bord[i][j];
    }
    if (dp[i][j] != -1) {                
        return dp[i][j];
    }
    if (bord[i][j] == 0) {
        return 0;
    }
    if (bord[i][j] == 1) {
        int ret = 0;        
        ret = min(count(bord, i + 1, j + 1), min(count(bord, i, j + 1), count(bord, i + 1, j))) + 1;
        ans = max(ans, ret);        
        dp[i][j] = ret;        
        return ret;
    }
    
}
int main(void) {
    cin >> n >> m;
    vector<vector<int>> bord(n);
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < n; i++) {
        string str;
        cin >> str;
        for (int j = 0; j < m; j++) {
            bord[i].push_back(str[j] -'0');            
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {            
            int trash = count(bord, i, j);
        }
    }
    cout << ans * ans << endl;
    return 0;
}