221. Maximal Square

진짜 오래간만에 알고리즘을 풀어봤습니다! 오래간만에 풀어보니, 어렵네요...

 

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

Maximal Square - LeetCode

문제 자체는 심플합니다. 해당 배열에서 최대로 가질 수 있는 정사각형을 찾으면 됩니다.

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0

        m, n = len(matrix), len(matrix[0])
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        max_side = 0

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if matrix[i - 1][j - 1] == '1':
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                    max_side = max(max_side, dp[i][j])

        return max_side ** 2

여기서 간단하게 설명하자면, 시간 복잡도는 O(m * n)이고 공간 복잡도는 O(m * n)입니다.

입력받은 배열을 조회합니다. 조회하면서 각 모서리의 최솟값을 찾은 뒤 우측하단 모서리 부분에 최솟값 +1을 갱신해 줍니다. 갱신한값과 해당위치의 값을 비교하여 최댓값을 저장합니다. 모든 값을 찾은 뒤 배열에서 최댓값의 제곱으로 정사각형의 크기를 반환하게 했습니다.