파이썬으로 이진 행렬에서 1로 이루어진 가장 큰 정사각형의 면적 찾기

이진 행렬(binary matrix)이 주어졌을 때, 행렬 안에서 1로만 이루어진 가장 큰 정사각형의 면적을 구하는 문제입니다.

예를 들어 입력 행렬이 다음과 같다면,

출력은 16이 됩니다. 가운데 4×4 크기의 1로 이루어진 정사각형이 존재하기 때문입니다(4 × 4 = 16).

접근 방법: 동적 계획법(DP)

이 문제는 동적 계획법을 사용하면 O(rows × cols) 시간 복잡도로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 셀에 해당 셀을 오른쪽 아래 꼭짓점으로 하는 가장 큰 정사각형의 한 변의 길이를 저장하는 것입니다.

알고리즘 단계

• 결과 변수 res를 0으로 초기화합니다.
• 첫 번째 열의 모든 값을 확인하여 res와 비교해 최댓값을 갱신합니다.
• 첫 번째 행의 모든 값도 마찬가지로 확인하여 res를 갱신합니다.
• i를 1부터 행 개수까지, j를 1부터 열 개수까지 반복하면서:
  • matrix[i][j]가 1이라면, 위쪽(matrix[i-1][j]), 왼쪽 대각선(matrix[i-1][j-1]), 왼쪽(matrix[i][j-1]) 세 값 중 최솟값에 1을 더한 값으로 갱신합니다.
  • res를 matrix[i][j]와 비교해 최댓값으로 갱신합니다.
• 최종적으로 res²(면적)를 반환합니다.

세 방향(위, 왼쪽, 대각선)의 최솟값에 1을 더하는 이유는, 현재 셀이 정사각형의 일부가 되려면 세 방향 모두 같은 크기 이상의 정사각형이 이미 형성되어 있어야 하기 때문입니다.

파이썬 구현 예제

class Solution:
    def solve(self, matrix):
        res = 0
        # 첫 번째 열 확인
        for i in range(len(matrix)):
            res = max(res, matrix[i][0])
        # 첫 번째 행 확인
        for i in range(len(matrix[0])):
            res = max(res, matrix[0][i])

        # 나머지 셀들을 동적 계획법으로 처리
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                if matrix[i][j] == 1:
                    matrix[i][j] = min(matrix[i - 1][j],
                                       matrix[i - 1][j - 1],
                                       matrix[i][j - 1]) + 1
                    res = max(res, matrix[i][j])

        return res * res

ob = Solution()
matrix = [
    [1, 0, 0, 0, 0, 1, 1],
    [0, 0, 0, 0, 0, 1, 1],
    [0, 1, 1, 1, 1, 0, 0],
    [0, 1, 1, 1, 1, 0, 0],
    [0, 1, 1, 1, 1, 0, 0],
    [0, 1, 1, 1, 1, 0, 0]
]
print(ob.solve(matrix))

입력

matrix = [
[1, 0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 1, 1],
[0, 1, 1, 1, 1, 0, 0],
[0, 1, 1, 1, 1, 0, 0],
[0, 1, 1, 1, 1, 0, 0],
[0, 1, 1, 1, 1, 0, 0]
]

출력

16

복잡도 분석

• 시간 복잡도: O(m × n) — 행렬의 모든 셀을 한 번씩만 방문합니다.
• 공간 복잡도: O(1) — 입력 행렬 자체를 DP 테이블로 활용하므로 추가 공간이 필요하지 않습니다.