[1915] 가장 큰 정사각형

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

요즘 나태해져서.. 다시 열심히 해야겠습니다 ㅎㅎ!!

DP문제입니다!

간단하게 생각하면 별로 안어려운 문제인 것 같습니다!

딱봐도..4인데... 어떻게 dp로 접근했냐하면

for문은 행우선으로 진행하면 됩니다. 행의 모든 열을 다 돌면 다음행!

그리고 중요한 것은 해당 배열의 위, 왼쪽, 그리고 왼쪽위 대각선 이 세방향을 검사했습니다.

내가 1이고 그 세 개중에 가장 작은 값(0은 제외) + 1이 결국 정사각형의 변의 길이입니다.

예제를 보면서 해결해보도록하죠!

4 4

0100

0111

1110

0010

dp테이블을 써보도록하겠습니다.

0100

0111

1120

0010

최대 변의 길이는 2겠지요!?!

그래서 정답은 2 * 2 = 4입니다!!!!!!!!!!!!!!

아래는 코드입니다.

#include <cstdio>
#define MAX_SIZE 1000
#define INF 0x7fffffff
 
bool arr[MAX_SIZE][MAX_SIZE];
int dp[MAX_SIZE][MAX_SIZE];
 
int min(int a, int b) {
    return a > b ? b : a;
}
 
int max(int a, int b) {
    return a > b ? a : b;
}
 
int main() {
 
    int m, n;
    scanf("%d %d", &m, &n);
 
 
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &arr[i][j]);
        }
    }
 
    int ret = 0;
    int dx[3] = { 0, -1, -1 };
    int dy[3] = { -1, 0, -1 };
 
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!arr[i][j]) continue;
 
            int min_value = INF;
            for (int k = 0; k < 3; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
 
                if (nx < 0 || ny < 0) {
                    min_value = 0;
                    break;
                }
                min_value = min(min_value, dp[nx][ny]);
            }
            if (!min_value) dp[i][j] = 1;
            else if (min_value != INF) dp[i][j] = min_value + 1;
 
            ret = max(dp[i][j], ret);
        }
    }
 
    printf("%d\n", ret * ret);
 
    return 0;
}