[C++] 리트코드 221. Maximal Square

class Solution 
{
public:
    int maximalSquare(vector<vector<char>>& matrix) 
    {
        //최대 사각형의 너비를 구하라
        int result = 0;
        int dp[300][300]{0};

        for(int m = 0; m < matrix.size(); m++)
        {
            if(matrix[m][0] == '1')
            {
                result = 1;
                dp[m][0] = 1;
            }
        }
        for(int n = 0; n < matrix[0].size(); n++)
        {
            if(matrix[0][n] == '1')
            {
                result = 1;
                dp[0][n] = 1;
            }
        }

        for(int m = 1; m < matrix.size(); m++)
        {
            for(int n = 1; n < matrix[m].size(); n++)
            {
                if(matrix[m][n] == '0')
                {
                    continue;
                }

                dp[m][n] = min(min(dp[m - 1][n - 1], dp[m - 1][n]), dp[m][n - 1]) + 1;
                result = max(dp[m][n], result);
            }
        }

        return result * result;
    }
};

 

풀이

1. 최대로 커질 수 있는 정사각형을 찾는다.

2. 왼쪽대각선, 상, 하의 값중 가장 작은 값에 + 1을 해준다.

11

11 일경우 2가 되는 것!

2가 되면 2*2의 정사각형이 완성된다.

3. 가장 큰 수의 제곱이 답이 된다.

 

 

 

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

LeetCode - The World's Leading Online Programming Learning Platform