[Algorithm] LeetCode 221. Maximal Square in Python(파이썬)

💡 LeetCode 221:

1로 이루어진 정사각형의 최대 면적 구하기

🌱 코드 in Python

알고리즘: Dynamic Programing

class Solution:
    def maximalSquare(self, matrix: list[list[str]]) -> int:
        ans = 0
        row = len(matrix)
        col = len(matrix[0])
        dp = [[0 for _ in range(col + 1)] for _ in range(row + 1)]
        for i in range(row):
            for j in range(col):
                if matrix[i][j] == "1":
                    dp[i + 1][j + 1] = min(dp[i][j], dp[i + 1][j], dp[i][j + 1]) + 1
                    ans = max(ans, dp[i + 1][j + 1])
        return ans * ans

우선 처음에는 0이 끼어있으면 무조건 정사각형이 망가진다! 라는 생각으로 풀이를 시작했다.
이 0을 어떻게 하면 처리할 수 있을까 보다가,
내가 1일때 나의 왼쪽 대각선 위, 나의 위, 나의 왼쪽에 하나라도 0이 있으면
면적을 1로 초기화해줘야 한다고 생각했다.
1이 1개라도 있으면 정사각형의 면적이 1이 되므로
if 나 == "1" 일때 갱신해 줄 수 있도록 하고
동시에 최소값의 + 1을 해줄 수 있도록 하였습니다.

🧠 기억하자

1. 최대면적 + 배열이니까 DP의 확률이 높다고 보고 접근할 수 있을 것 같다.
2. 규칙을 좀 빨랑 빨랑 좀 파악하자!

LeetCode 221 바로가기