이 문제에서는 m × n 크기의 이진 행렬(binary matrix)이 주어졌을 때, 모든 원소가 1인 부분 행렬(submatrix)이 총 몇 개 존재하는지 구해야 합니다.
예를 들어 입력 행렬이 다음과 같다고 가정해 보겠습니다.
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 1 | 1 |
이 경우 출력은 13입니다. 크기별로 살펴보면 1×1 부분 행렬 6개, 2×1 부분 행렬 3개, 1×2 부분 행렬 2개, 3×1 부분 행렬 1개, 그리고 2×2 부분 행렬 1개가 존재하여 전체 13개가 됩니다.
문제 해결 접근 방법
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 칸을 기준으로 위쪽 방향으로 연속된 1의 개수를 미리 계산해 두는 것입니다.
구체적인 단계는 다음과 같습니다.
m := 행렬의 행(row) 개수
n := 행렬의 열(column) 개수
dp := 같은 크기(m × n)의 0으로 초기화된 행렬 생성
i를 0부터 m-1까지 반복:
j를 0부터 n-1까지 반복:
첫 번째 행(i = 0)이고 matrix[i][j]가 1이면, dp[i][j] := 1
그 외의 경우 matrix[i][j]가 0이 아니면, dp[i][j] := dp[i-1][j] + 1
total := 0 으로 초기화
i를 0부터 m-1까지 반복:
j를 0부터 n-1까지 반복:
k를 j+1부터 n까지 반복하며, total += min(dp[i][j:k]) (즉, j부터 k까지 구간의 최솟값을 누적)
total 반환
여기서 dp[i][j]는 (i, j) 위치에서 위쪽 방향으로 연속해서 나타나는 1의 개수, 즉 각 열을 히스토그램의 높이처럼 바라본 값입니다. 각 행을 밑변으로 하는 모든 열 구간에 대해 구간 내 최소 높이만큼의 부분 행렬을 만들 수 있으므로, 이 최솟값들을 모두 더하면 정답을 얻을 수 있습니다.
예제 코드
def solve(matrix):
m = len(matrix)
n = len(matrix[0])
dp = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if i == 0 and matrix[i][j]:
dp[i][j] = 1
elif matrix[i][j]:
dp[i][j] = dp[i-1][j] + 1
total = 0
for i in range(m):
for j in range(n):
for k in range(j+1, n+1):
total += min(dp[i][j:k])
return total
matrix = [[1,0,1],[0,1,1],[0,1,1]]
print(solve(matrix))입력
[[1,0,1],[0,1,1],[0,1,1]]
출력
13
시간 복잡도 분석
위 코드는 dp 테이블을 채우는 데 O(m × n), 각 행마다 가능한 모든 열 구간(j, k)을 검사하는 데 O(n²)이 걸리므로, 전체 시간 복잡도는 O(m × n²)입니다. 공간 복잡도는 dp 테이블 저장에 O(m × n)이 필요합니다.
참고로, 각 행마다 스택(stack) 기반의 히스토그램 기법을 적용하면 열 구간 탐색을 O(n)으로 줄여 전체 시간 복잡도를 O(m × n)까지 개선할 수 있습니다. 다만 위 방법은 직관적이고 구현이 간단하여 문제의 원리를 이해하기에 매우 적합합니다.