가장 큰 정사각형 찾기

코드

(효율성 테스트 실패 코드)

#include <iostream>
#include<vector>
using namespace std;

int solution(vector<vector<int>> board)
{
    int ans = 0;
    for(int i=0;i<board.size();i++)
    {
        for(int j=0;j<board[i].size();j++)
        {
            if(!board[i][j]) continue;
            int size=0;
            while(true)
            {
                int flag = 0;
                for(int ii=0;ii<=size;ii++)
                {
                    for(int jj=0;jj<=size;jj++)
                    {
                        int ni = i + ii;
                        int nj = j + jj;
                        if(ni >= board.size() || nj>=board[0].size()) {
                            flag = 1;
                            break;
                        }
                        if(board[ni][nj] == 0) {
                            flag = 1;
                            break;
                        }
                    }
                    if(flag == 1) break;
                }
                if(flag == 0) size++;
                else break;
            }
            ans = max(size*size,ans);
            if(ans == min(board.size(), board[0].size()))
                return ans;
        }
    }
    return ans;
}

---

정답 코드

#include <iostream>
#include<vector>
using namespace std;

int solution(vector<vector<int>> board)
{
    int ans = 0;
    /* 가로, 세로 모두 길이가 1이면 */
    if(board.size()==1 and board[0].size()==1) return board[0][0];

    for(int i=0;i<board.size();i++)
    {
        for(int j=0;j<board[i].size();j++)
        {
            if(!board[i][j]) continue;
            /* 가로 or 세로의 길이가 1일 때를 대비한 코드 */
            if(!i or !j) {
                ans = max(1,ans);
                continue;
            }
            if(board[i-1][j] and board[i][j-1] and board[i-1][j-1]){
                board[i][j] = min(board[i-1][j-1],min(board[i][j-1], board[i-1][j])) + 1;
                ans = max(ans,board[i][j]*board[i][j]);
            }
        }
    }
    return ans;
}

• key point!
  : DP로 생각하는 사고방식을 떠올려야 함ㅠ
• 원리
  : 큰 정사각형을 이루는 조건은 작은 정사각형을 이루는 조건으로 표현될 수 있다.
  D[i][j] = min(D[i-1][[j-1], min(D[i][j-1],D[i-1][j])) + 1;