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

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

 

가장 먼저, 완전 탐색 풀이를 적어보고 시간복잡도가 효율성을 통과할 수 있을지 확인해보자.

완전탐색으로 푼다면, 직사각형의 크기가 N x M 일 때 가능한 정사각형 한변의 길이 k에 대하여 모든 k*k를 확인해야 한다.

따라서 다음과 같이 5중 포문을 써야 하고 결국 TLE가 날 것임을 예상할 수 있다.

 

for (int k = 1; k<min(N, M), k++) { //가능한 정사각형 한변의 길이

    for (int i=0; i<=N-k; i++) // 정사각형의 시작점 (i, j)  

        for (int j=0; j<=M-k; j++) 

            for (int l=i; l<i+k; l++) //k*k가 1인지 확인

               for (int m=j; m<j+k; m++) 

 

 

완탐이 불가능할 때 dp가 가능한지 생각해보면 좋은데, 해당 문제는 dp로 간단히 해결할 수 있다.

dp[i][j] 를 (i, j)를 오른쪽 끝점으로 하는 정사각형의 최대 한변의 길이 라고 설정했을 때, 점화식은 다음과 같다.

 

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i][j]) + 1 (단, board[i][j] 값이 1이어야 함)

 

board[i][j] = 1일 때, 이를 오른쪽 아래 꼭짓점으로 하는 정사각형을 만들 수 있다.

만들 수 있는 정사각형의 최대 한변 길이는 왼쪽, 위쪽, 대각선 방향으로의 최대 정사각형을 살펴 결정할 수 있는데, 각 방향에서 만들 수 있는 최대 정사각형의 한변 길이에 대하여 이들의 최솟값에 1을 더한 것이 dp[i][j] 값이 된다.

 

이 때, i = 0 이거나 j = 0인 경우 board[i][j] = 1 이면 한변의 길이가 1인 정사각형을 만들 수 있으므로, 다음과 같이 예외처리한다.

 

dp[i][j] = board[i][j] (i == 0 이거나 j == 0)

 

문제에서는 만들수 있는 최대 정사각형의 크기를 요구한다.

따라서, i와 j 를 순회하면서 dp[i][j]의 최댓값 mx를 찾고 mx*mx를 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int solution(vector<vector<int>> board) {
    
    int H = board.size();
    int W = board[0].size();
    vector<vector<int>> dp(H, vector<int>(W, 0));
    
    for (int i=0; i<H; i++) {
        for (int j=0; j<W; j++) {
            if (i == 0 || j == 0) dp[i][j] = board[i][j]; 
            else if (!board[i][j]) continue;
            else dp[i][j] = min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]})+1;
        }
    }

    int mx = 0;
    for (int i=0; i<H; i++) {
        for (int j=0; j<W; j++)
            mx = max(dp[i][j], mx);
    }
    return mx*mx;
}