221. Maximal Square

 

https://leetcode.com/problems/maximal-square/

Maximal Square - LeetCode

문제 조건 및 풀이

1과 0으로 이루어진 2차원 배열이 주어졌을 때, 1로만 채워진 최대 크기의 정사각형을 구하는 문제. 떠올릴 수 있는 가장 간단한 방법은 모든 경우의 수를 다 구해보는 brute force 방식이다. 이렇게 풀더라도 문제를 통과할 수는 있다고 한다. 맨 좌측 상단부터 크기가 1, 2... k(k는 가로, 세로 중 작은 값) 인 정사각형이 존재하는지 모두 확인하는 코드를 작성하면 된다. 이 경우의 시간복잡도는

- 각 좌표를 선택 : O(mn)

- 한 좌표를 좌상단 꼭짓점으로 지정했을 때, 크기가 1, 2, ... k 인 정사각형을 탐색하는 횟수 : O(k^2)

이므로 O(mnk^2)가 되는데, 간단하게 O((mn)^2)으로 표기할 수 있다.

한편 DP로도 문제를 풀 수 있다. 아이디어는 어떤 좌표 (x, y)가 있을 때, 그 좌표를 둘러싼 좌측 or 상단의 좌표들이 정사각형을 이루고 있는 경우 해당 좌표까지 포함한 정사각형을 생성할 수 있다는 것이다.

위 그림처럼 초록, 노랑, 주황 정사각형은 각각 길이 1, 2의 정사각형이다. 흰색으로 칠해진 좌표를 좌하단으로 삼는 최대 크기의 정사각형은 길이 3이 된다.

이 그림은 주황색 정사각형이 크기 1인 정사각형이 될 경우이다. 이 경우 흰색으로 칠해진 좌표를 좌하단으로 삼는 최대 크기의 정사각형은 2가 된다. 이 아이디어를 점화식으로 표현하면 다음과 같다.

dp[x][y] = min(dp[x-1][y], dp[x][y-1], dp[x-1][y-1]) + 1

코드

#define row 301
#define col 301
class Solution {
public:
    int max(int a, int b) {
        return a>b ? a : b;
    }
    
    int maximalSquare(vector<vector<char>>& matrix) {
        int dp[row][col] = {0, };
        
        int answer = 0;
        for (int i = 1; i<= matrix.size() ; i++) {
            for (int j = 1; j <= matrix[0].size() ; j++) {
                if (matrix[i-1][j-1] == '0') continue;
                
                dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1;
                answer = max(answer, dp[i][j]);
            }
        }
        
        return answer*answer;
    }
};