[Leetcode 221] Maximal Square

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

1) 코드

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

        dp = [[0]*n for _ in range(m)]
        max_side = 0 

        for i in range(m):
            if matrix[i][0] == "1":
                dp[i][0] = 1 
                max_side = max(max_side, dp[i][0])

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

        return max_side*max_side

2) 해설

• DP를 활용해서 Maximal Square를 구하는 문제이다.
• dp[i][j] = 1 + min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1])
  이 로직이 핵심이다
  -> 이 로직이 왜 성립할 수 있는지는 그림을 그려서 작성해보면
  쉽게 이해갈 수 있다.