가장 큰 정사각형 찾기

1. 문제

문제 설명

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

예를 들어

1 2 3 4

0 1 1 1

1 1 1 1

1 1 1 1

0 0 1 0

가 있다면 가장 큰 정사각형은

1 2 3 4

0 1 1 1

1 1 1 1

1 1 1 1

0 0 1 0

가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.

제한사항

표(board)는 2차원 배열로 주어집니다.

표(board)의 행(row)의 크기 : 1000 이하의 자연수

표(board)의 열(column)의 크기 : 1000 이하의 자연수

표(board)의 값은 1또는 0으로만 이루어져 있습니다.

입출력 예

board answer

[[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9

[[0,0,1,1],[1,1,1,1]] 4

입출력 예 설명

입출력 예 #1

위의 예시와 같습니다.

입출력 예 #2

| 0 | 0 | 1 | 1 |

| 1 | 1 | 1 | 1 | 

로 가장 큰 정사각형의 넓이는 4가 되므로 4를 return합니다.

2. 알고리즘

키워드 - DP

3. 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

#include <iostream>   #include<vector>   using namespace std;   int calcMX(const vector<vector<int>>& psum, int endY, int endX) {       int hi = 1001;    // 답이 안되는걸 나타냄     int lo = 0;     int mid = 0;       while (lo + 1 < hi)     {         mid = (lo+hi)/2;         bool ok = true;         int beginY = endY - mid + 1;         int beginX = endX - mid + 1;           if (beginY < 0 || beginX < 0)             ok = false;           int sum = 0;           if (ok)             sum = psum[endY][endX] - (beginY == 0 ? 0 : psum[beginY-1][endX]) -(beginX == 0 ? 0 : psum[endY][beginX - 1])                     + ((beginX == 0 || beginY == 0) ? 0 : psum[beginY - 1][beginX - 1]);           if (sum != mid * mid)             ok = false;           if (ok == true)             lo = mid;         else              hi = mid;     }     return lo; }   int solution(vector<vector<int>> board) {     int answer = 1234;     int size = board.size();     vector<vector<int>> psum = board;       psum[0][0] = board[0][0];     for (int i = 1; i < board[0].size(); ++i)         psum[0][i] = psum[0][i - 1] + board[0][i];       for (int i = 1; i < board.size(); ++i)         psum[i][0] = psum[i - 1][0] + board[i][0];           for (int i = 1; i < board.size(); ++i)         for (int j = 1; j < board[0].size(); ++j)             psum[i][j] = psum[i-1][j] + psum[i][j-1] + board[i][j] - psum[i-1][j-1];       int sol = 0;     for (int i = 0; i < psum.size(); ++i)         for (int j = 0; j < psum[0].size(); ++j) {             sol = max(sol, calcMX(psum, i, j));    // logN         }     return sol * sol; } Colored by Color Scripter

cs