[Leetcode/파이썬] 221. Maximal Square

Maximal Square

---

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

 

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Example 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

Example 3:

Input: matrix = [["0"]]
Output: 0

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] is '0' or '1'.

 

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        res = 0

        for i in range(len(matrix)) :
            for j in range(len(matrix[0])) :
                matrix[i][j] = int(matrix[i][j])
                res = max(res, matrix[i][j])

                if i-1 >= 0 and j-1 >= 0 :
                    if matrix[i][j] >= 1 \
                        and matrix[i-1][j-1] >= 1 \
                        and matrix[i-1][j] >= 1 \
                        and matrix[i][j-1] >= 1 :
                            tmp = min(matrix[i-1][j-1], matrix[i][j-1], matrix[i-1][j])
                            matrix[i][j] = tmp + 1
                            res = max(res, matrix[i][j])

        return res ** 2

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        n, m = len(matrix), len(matrix[0])

        res = 0
        for i in range(n) :
            for j in range(m) :
                matrix[i][j] = int(matrix[i][j])
                res = max(res, matrix[i][j])

                if matrix[i][j] and i and j :
                    tmp = min(matrix[i-1][j-1], matrix[i][j-1], matrix[i-1][j])
                    matrix[i][j] = tmp + 1
                    res = max(matrix[i][j], res)

        return res ** 2

공부하면서 이거저거 해보다가 이런 방식으로 풀어보았다. 요즘 문제들이 점점 어려워져서 답안을 확인하는 게 습관화 되는것 같아 무섭다. 이번 역시 첫번째 풀이를 참고하여 이래저래 또 다른 답안을 알아보다가 두 번째 풀이가 나오게 되었다.

풀이는... 모르겠다 다시 공부해 봐야지

--------------------------------------------------------------------------------------------

큰 문제를 작게 쪼개서 계산하는 문제로, 1을 구하고, 좌상단, 좌측, 상단 에서 1이라면 그 다음 2, ... 계속해서 넘어가는 동적계획법, 다이나믹 프로그래밍을 떠올려보자.

아주 작은 1의 넓이를 가진 정사각형 부터 시작해서 3개의 가장 가까운 사각형의 넓이가 얼마인지 계산한다. 그 중 가장 작은것만 뽑아서 수를 갱신하고, 가장 큰 정사각형 한 변의 길이를 갱신한다. 

어찌보면 다이나믹 프로그래밍을 제대로 이해하고 있다면 풀 수 있는 문제라고 생각한다. 다시 확인해봐야겠다.