221. Maximal Square

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

Maximal Square - LeetCode

 

최대 정사각형을 찾는 문제이다.

DP로 풀면되는데,

 

정사각형의 넓이를 리턴하면 된다.

 

매트릭스의 값이 1일 때 

 

왼쪽, 왼쪽 위, 위,  세가지의 값중 최소값에 1을 더하면 

 

dp_arr에서

최대로 만들 수있는 정사각형 변을 알 수 있다.

 

max_value를 항상 최대값으로 업데이트 해주면서 

 

마지막으로 변의 제곱을 리턴해주면 된다.

 

 

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """

        
        
        dp_arr = [ [0 for i in range(len(matrix[0]))] for j in range(len(matrix))]
        
       
        
        max_value = 0
        for i in range(0, len(matrix),1):
            
            for j in range(0, len(matrix[0]),1):
                
                if i == 0 or j == 0:
                    dp_arr[i][j] = int(matrix[i][j])
                    max_value = max(max_value, dp_arr[i][j])
                else:
                    #print(i,j, matrix[i][j])    
                    if int(matrix[i][j]) == 1:
                        #print(i,j,"WOWLS?")
                        dp_arr[i][j] = min(dp_arr[i-1][j], dp_arr[i][j-1], dp_arr[i-1][j-1])+1
                        max_value = max(max_value, dp_arr[i][j])
                        #print(max_value,"MAX_VALUE")
    
        return max_value*max_value