가장 큰 영 부분 행렬 찾기¶
n개의 행과 m개의 열로 이루어진 행렬이 주어집니다. 0으로만 이루어진 가장 큰 부분 행렬을 찾으십시오(부분 행렬은 행렬의 직사각형 영역입니다).
알고리즘¶
행렬의 원소는 a[i][j]이며, 여기서 i = 0...n - 1, j = 0... m - 1입니다. 간단히 하기 위해 0이 아닌 모든 원소는 1로 간주하겠습니다.
1단계: 보조 동적 계획법¶
먼저 다음과 같은 보조 행렬 d[i][j]를 계산합니다. 이는 a[i][j]의 위쪽에서 1이 있는 가장 가까운 행입니다. 형식적으로 말하면, d[i][j]는 j번째 열에 1과 같은 원소가 있는 가장 큰 행 번호(0부터 i - 1까지)입니다. 왼쪽 위에서 오른쪽 아래로 순회하면서 행 i에 있을 때는 이전 행의 값을 이미 알고 있으므로, 값이 1인 원소만 갱신하면 충분합니다. 이후 알고리즘에서는 행렬을 한 번에 한 행씩 처리하며 현재 행의 값만 필요하므로, 값들을 단순한 배열 d[i], i = 1...m - 1에 저장할 수 있습니다.
vector<int> d(m, -1);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (a[i][j] == 1) {
d[j] = i;
}
}
}
2단계: 문제 해결¶
행을 순회하면서 부분 행렬의 가능한 모든 왼쪽 열과 오른쪽 열을 고려하면 $O(n m^2)$에 문제를 해결할 수 있습니다. 직사각형의 아래쪽은 현재 행이 되며, d[i][j]를 사용하여 위쪽 행을 찾을 수 있습니다. 그러나 더 나아가 풀이의 복잡도를 크게 개선할 수 있습니다.
구하려는 영 부분 행렬은 네 변 모두가 어떤 1들로 막혀 있으며, 이 1들 때문에 크기를 늘려 답을 개선할 수 없다는 것은 분명합니다. 따라서 다음과 같이 하면 답을 놓치지 않습니다. 행 i(영 부분 행렬이 될 수 있는 영역의 가장 아래 행)의 모든 칸 j에 대해 d[i][j]를 현재 영 부분 행렬의 위쪽 행으로 삼습니다. 이제 남은 것은 영 부분 행렬의 최적의 왼쪽 경계와 오른쪽 경계를 정하는 것, 즉 이 부분 행렬을 j번째 열의 왼쪽과 오른쪽으로 최대한 밀어내는 것입니다.
왼쪽으로 최대한 밀어낸다는 것은 무엇을 의미합니까? 이는 d[i][k1] > d[i][j]를 만족하는 인덱스 k1을 찾는 것을 의미하며, 동시에 k1은 인덱스 j의 왼쪽에서 가장 가까운 인덱스여야 합니다. 그러면 k1 + 1이 구하려는 영 부분 행렬의 왼쪽 열 번호가 된다는 것은 분명합니다. 그러한 인덱스가 전혀 없다면 k1 = -1로 둡니다(이는 현재 영 부분 행렬을 왼쪽으로 행렬 a의 경계까지 확장할 수 있었다는 뜻입니다).
대칭적으로 오른쪽 경계에 대한 인덱스 k2를 정의할 수 있습니다. 이는 d[i][k2] > d[i][j]를 만족하는, j의 오른쪽에서 가장 가까운 인덱스입니다(그러한 인덱스가 없다면 m입니다).
따라서 인덱스 k1과 k2를 효율적으로 찾는 방법을 알게 되면, 이 인덱스들이 현재 영 부분 행렬에 대해 필요한 모든 정보를 제공합니다. 특히 그 넓이는 (i - d[i][j]) * (k2 - k1 - 1)과 같습니다.
i와 j가 고정되어 있을 때 이 인덱스 k1과 k2를 어떻게 효율적으로 찾을 수 있습니까? 이는 평균 $O(1)$에 할 수 있습니다.
이러한 복잡도를 달성하려면 다음과 같이 스택을 사용할 수 있습니다. 먼저 인덱스 k1을 찾는 방법을 알아보고, 현재 행 i 안의 각 인덱스 j에 대해 그 값을 행렬 d1[i][j]에 저장합시다. 이를 위해 모든 열 j를 왼쪽에서 오른쪽으로 살펴보며, d[][]가 d[i][j]보다 엄격하게 큰 열만 스택에 저장합니다. 열 j에서 다음 열로 이동할 때 스택의 내용을 갱신해야 한다는 것은 분명합니다. 스택의 맨 위에 부적절한 원소(즉, d[][] <= d[i][j])가 있으면 그것을 꺼냅니다. 스택에서 원소를 제거할 때는 맨 위에서만 제거하면 충분하고 다른 위치에서는 제거할 필요가 없다는 것을 쉽게 알 수 있습니다(스택에는 열들이 d 값이 증가하는 순서로 담겨 있기 때문입니다).
각 j에 대한 값 d1[i][j]는 그 순간 스택의 맨 위에 있는 값과 같습니다.
인덱스 k2를 찾기 위한 동적 계획법 d2[i][j]도 비슷하게 계산하며, 다만 열을 오른쪽에서 왼쪽으로 살펴보아야 합니다.
각 행마다 스택에 정확히 m개가 추가되므로 삭제도 그보다 많을 수 없고, 복잡도의 합은 선형이 됩니다. 따라서 알고리즘의 최종 복잡도는 $O(nm)$입니다.
또한 이 알고리즘은 $O(m)$의 메모리를 사용한다는 점도 짚어 두어야 합니다(입력 데이터인 행렬 a[][]는 제외합니다).
구현¶
int zero_matrix(vector<vector<int>> a) {
int n = a.size();
int m = a[0].size();
int ans = 0;
vector<int> d(m, -1), d1(m), d2(m);
stack<int> st;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (a[i][j] == 1)
d[j] = i;
}
for (int j = 0; j < m; ++j) {
while (!st.empty() && d[st.top()] <= d[j])
st.pop();
d1[j] = st.empty() ? -1 : st.top();
st.push(j);
}
while (!st.empty())
st.pop();
for (int j = m - 1; j >= 0; --j) {
while (!st.empty() && d[st.top()] <= d[j])
st.pop();
d2[j] = st.empty() ? m : st.top();
st.push(j);
}
while (!st.empty())
st.pop();
for (int j = 0; j < m; ++j)
ans = max(ans, (i - d[j]) * (d2[j] - d1[j] - 1));
}
return ans;
}