파이썬으로 이진 행렬 속 모든 1로 이루어진 정사각형 부분 행렬 개수 계산하기

문제 소개

2차원 이진 행렬(binary matrix)이 주어졌을 때, 모든 원소가 1로 이루어진 정사각형 부분 행렬이 몇 개나 존재하는지 구해야 합니다.

예를 들어, 다음과 같은 행렬이 입력으로 주어진다고 가정해 보겠습니다.

이 경우 출력은 5가 됩니다. 크기가 (2 × 2)인 정사각형이 하나 있고, (1 × 1)짜리 작은 정사각형이 네 개 있기 때문입니다.

해결 접근법: 동적 프로그래밍(DP)

이 문제는 동적 프로그래밍 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 행렬의 각 위치 (i, j)에서, 해당 칸이 정사각형의 오른쪽 아래 꼭짓점일 때 만들 수 있는 가장 큰 정사각형의 한 변 길이를 저장합니다.
• 그 값은 왼쪽 위 대각선(mat[i-1][j-1]), 왼쪽(mat[i][j-1]), 바로 위(mat[i-1][j]) 세 값 중 최솟값에 1을 더한 것과 같습니다.
• 모든 위치의 값을 누적하면 전체 정사각형의 개수를 얻을 수 있습니다. 예를 들어 어떤 칸의 값이 3이라면, 그 칸에서 끝나는 (1×1), (2×2), (3×3) 정사각형 세 개가 존재한다는 의미입니다.

구체적인 알고리즘 단계는 다음과 같습니다.

• 행렬 mat이 비어 있다면 0을 반환합니다.
• 카운터 c := 0으로 초기화합니다.
• 모든 행 i와 열 j에 대해 반복합니다.
  • mat[i][j]가 1이면:
    • i == 0 또는 j == 0이면(첫 번째 행 또는 첫 번째 열) c를 1 증가시킵니다.
    • 그렇지 않으면 temp = min(mat[i-1][j-1], mat[i][j-1], mat[i-1][j]) + mat[i][j]를 계산하고, c += temp, mat[i][j] = temp로 갱신합니다.
• 최종적으로 c를 반환합니다.

입력 행렬 자체를 DP 테이블로 활용하므로 별도의 추가 메모리가 필요 없으며, 시간 복잡도는 O(m×n), 공간 복잡도는 O(1)로 매우 효율적입니다.

예제 코드

다음 구현을 통해 더 잘 이해해 보겠습니다.

def solve(mat):
    if mat == []:
        return 0
    c = 0

    for i in range(len(mat)):
        for j in range(len(mat[0])):
            if mat[i][j] == 1:
                if i == 0 or j == 0:
                    c += 1
                else:
                    temp = (min(mat[i - 1][j - 1], mat[i][j - 1], mat[i - 1][j]) + mat[i][j])
                    c += temp
                    mat[i][j] = temp
    return c

matrix = [
   [0, 1, 1],
   [0, 1, 1]
]
print(solve(matrix))

입력

[[0, 1, 1], [0, 1, 1]]

출력

5

정리

동적 프로그래밍을 활용하면 브루트 포스 방식(O((mn)²) 이상)보다 훨씬 빠르게 정사각형 부분 행렬의 개수를 구할 수 있습니다. 이 알고리즘은 '최대 정사각형 찾기' 문제와 유사한 패턴을 공유하므로, DP 유형 문제 학습에도 큰 도움이 됩니다.