백준 1915 [복습필수]

 

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

1915번: 가장 큰 정사각형

 

처음 접근법 (실패)

DFS (재귀) 이용

DFS 호출할 때마다 cnt 증가 (cnt: 정사각형 한 변의 길이를 의미)

오른쪽, 아래쪽, 오른쪽 아래 대각선이 모두 1이면 dp[i][j] = cnt

하나라도 0이거나 범위를 벗어나면 탐색 불가 (return 0 또는 cnt-1)

 

두 번째 접근법 (https://yabmoons.tistory.com/158)

위 블로그 설명에서는 왼쪽, 위쪽, 왼쪽 위 대각선을 탐색했는데,

나는 오른쪽, 아래쪽, 오른쪽 아래 대각선을 탐색해도 될 거라고 판단

하지만, 내가 생각한 방법대로 하면 한 번 계산한 행 (또는 열)은 다음 계산에 반영 안됨.

블로그 설명대로 왼쪽, 위쪽, 왼쪽 위 대각선을 탐색한다면 한 번 계산한 행 (또는 열)도 다음 계산에 반영됨.

 

진행과정

012345678

#include <iostream>
#include <algorithm>
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
int n, m, dp[1001][1001], ans;
void input();
void func() {
    rep(i, n) {
        rep(j, m) {
            if (dp[i][j] == 1)
                dp[i][j] = min(dp[i][j - 1], min(dp[i - 1][j - 1], dp[i - 1][j])) + 1;
            ans = max(ans, dp[i][j]);
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    input();
    func();
    cout << ans * ans;
}
void input() {
    cin >> n >> m;
    rep(i, n) {
        rep(j, m) {
            char c;
            cin >> c;
            dp[i][j]= c - '0';
        }
    }
}