[LeetCode] 221. Maximal Square

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

 

 

이 문제를 풀기 위해서 nested for loop을 사용했습니다.

Input n x m 에 맞춰 각 반복문에서 현재 위치 기준으로 좌단, 상단, 좌상단 index를 모두 확인하여 그 중 최솟값에 + 1을 하는 전략을 취했습니다. 

만약 현재 인덱스가 0이라면 해당 위치에서 구성할 수 있는 최대 사각형의 넓이 또한 0이므로, 즉시 다음 반복문으로 넘어갑니다. 

매 반복문의 마지막에 max_num을 업데이트 해주면서, 최종적으로 길이의 제곱을 반환해 넓이 값을 리턴합니다. 

def maximalSquare(self, matrix: List[List[str]]) -> int:
    n = len(matrix)
    m = len(matrix[0])
    dp = [[0] * m for _ in range(n)]

    max_num = 0
    for i in range(n):
        for j in range(m):
            if matrix[i][j] == "0":
                continue
            left = top = diag = 0
            if i > 0: left = int(dp[i-1][j])
            if j > 0: top = int(dp[i][j-1])
            if (i > 0) and (j > 0): diag = int(dp[i-1][j-1])
            dp[i][j] = min(left, top, diag) + 1

            max_num = max(dp[i][j], max_num)

    return max_num ** 2

 

살짝 efficiency를 다듬은 코드는 다음과 같습니다. 

def maximalSquare(self, matrix: List[List[str]]) -> int:
    n = len(matrix)
    m = len(matrix[0])
    dp = [[0] * m for _ in range(n)]

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

    return max_num ** 2