[BAEKJOON] 1915 가장 큰 정사각형

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; int row, col; vector<vector<int>>map(1001, vector<int>(1001)); vector<vector<int>>DP(1001, vector<int>(1001, -1)); int square(int x,int y) { if (x == row - 1 || y == col - 1) return map[x][y]; if (map[x][y] == 0) return 0; int &ret = DP[x][y]; if (ret != -1) return ret; int num1 = 0, num2 = 0,num3 = 0; if (x + 1 < row) num1 = square(x + 1, y); if (y + 1 < col) num2 = square(x, y + 1); if (x + 1 < row && y + 1 < col) num3 = square(x + 1, y + 1); return ret = min(num1, min(num2, num3)) + 1; } int main() { scanf("%d %d", &row, &col); string input; for (int x = 0; x < row; x++) { cin >> input; for (int y = 0; y < col; y++) map[x][y] = input[y]-'0'; } int Max = 0; for (int x = 0; x < row; x++) for (int y = 0; y < col; y++) Max = max(Max, square(x, y)); printf("%d", Max*Max); return 0; }