221. Maximal Square ★

221. Maximal Square

 

이 문제는 m×n 크기의 **이진 행렬(binary matrix)**이 주어졌을 때,

1로만 구성된 가장 큰 정사각형을 찾아 그 **면적(area)**을 반환하는 문제입니다.

---

문제를 이해하기 위한 주요 포인트

1. 입력 형식:
   • 이진 행렬(matrix): m×n 크기의 리스트로, 각 원소는 문자열 "0" 또는 "1"입니다.
2. 목표:
   • "1"로만 구성된 가장 큰 정사각형의 한 변의 길이를 구하고, 그 면적(한 변의 길이의 제곱)을 반환합니다.
3. 출력 형식:
   • 정사각형의 면적을 나타내는 정수 값.
4. 조건:
   • 정사각형은 반드시 연속된 1로 구성되어야 합니다.

 

해결 방법

이 문제는 **동적 계획법(Dynamic Programming, DP)**을 사용하여 효율적으로 해결할 수 있습니다.

핵심 아이디어

• dp[i][j]를 정의:
  • dp[i][j]: (i,j) 위치를 오른쪽 아래 모서리로 하는 가장 큰 정사각형의 한 변의 길이.
• 점화식:
  • matrix[i][j]="1" 인 경우:
    • dp[i][j] = min⁡( dp[i−1][j], dp[i][j−1], dp[i−1][j−1] ) + 1
    • 의미: 현재 위치를 포함한 정사각형의 크기는 왼쪽, 위쪽, 대각선 위의 최소값에 1을 더한 값.
• 초기 조건:
  • 첫 행이나 첫 열에서는 정사각형의 크기가 1 또는 0입니다.
• 최대값 추적:
  • dp[i][j]의 최대값을 지속적으로 추적하여, 최종 면적을 계산합니다.

---

시간 및 공간 복잡도

1. 시간 복잡도:
   • 행렬 전체를 한 번 순회하므로 O(m×n).
2. 공간 복잡도:
   • 추가로 O(m×n) 크기의 DP 배열을 사용.

최소값을 사용하는 이유는,

정사각형을 구성하는 데 모든 방향이 제한 요소가 되기 때문입니다.

최소값을 기준으로 현재 위치를 포함하면, 가장 큰 정사각형의 크기를 올바르게 계산할 수 있습니다.

 

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

        m = len(matrix)
        n = len(matrix[0])

        dp = [([0] * n) for _ in range(m)]
        maxSize = 0 # 최대 정사각형 한 변의 길이

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == "1":  # 현재 위치가 "1"인 경우
                    if i==0 or j==0:  # 첫 행 또는 첫 열인 경우
                        # 이 위치에서는 1x1 크기의 정사각형 이므로,
                        dp[i][j] = 1
                    else:
                        # 현재 위치를 포함한 정사각형의 크기는 
                        # 왼쪽, 위쪽, 대각선 위의 최소값에 1을 더한 값.
                        # 왜 최소값?
                        # 정사각형 크기를 키우려면,
                        # dp[i-1][j-1], dp[i-1][j], dp[i][j-1] 모두 1이어야 함. 
                        dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 
                    # 최대값 갱신
                    maxSize = max(maxSize, dp[i][j])

        return maxSize*maxSize # 면적 반환