[프로그래머스] 가장 큰 정사각형 찾기

https://programmers.co.kr/learn/courses/30/lessons/12905

코딩테스트 연습 - 가장 큰 정사각형 찾기

---

 

풀이

풀이는 dp를 이용해서 문제를 해결했다.

해당칸이 1이라면, 자신의 좌, 좌상, 상 부분을 검사해준다. 이때 3구역중 가장 작은부분+1을 해준것이, 해당칸을 포함한 정사각형의 변이 된다.

 

시간복잡도

2차원배열을 독립적으로 두번만 탐색하면되므로, O(N²)이 된다.

 

코드

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

int dp[1001][1001]={0};
int arr[1001][1001]={0};
int solution(vector<vector<int>> board)
{
    int answer=0;
    int h=board.size();
    int w=board[0].size();
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            arr[i+1][j+1]=board[i][j];
        }
    }
    
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            if(arr[i][j]==1){
                dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                answer=max(answer,dp[i][j]);
            }
        }
    }

    return answer*answer;
}