문제 개요
하나의 이진 행렬(0과 1로만 구성된 행렬)이 주어졌다고 가정해 보겠습니다. 우리가 구해야 하는 것은 한 개의 행(row)을 뒤집은 후, 한 개의 열(column)을 뒤집을 때 얻을 수 있는 1의 최대 개수입니다.
예를 들어, 입력 행렬이 다음과 같다면:
| 1 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
출력 결과는 8이 됩니다.
해결 접근 방법
이 문제는 모든 경우의 수를 직접 시뮬레이션하는 대신, 각 행과 열에 포함된 1의 개수를 미리 계산해 두면 O(n×m) 시간 안에 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
행 i를 뒤집으면 해당 행의 1은 0으로, 0은 1로 바뀝니다.
열 j를 뒤집으면 해당 열의 값들도 마찬가지로 반전됩니다.
단, 교차점인 셀 (i, j)는 행 뒤집기와 열 뒤집기로 두 번 뒤집히므로 원래 값으로 되돌아갑니다. 이를 보정하는 것이 이 알고리즘의 핵심입니다.
알고리즘 단계
n := 행렬의 행 개수
m := 행렬의 열 개수
ret := 0 (최종 결과값)
크기가 n인 배열 row 정의 (각 행별 1의 개수 저장)
크기가 m인 배열 col 정의 (각 열별 1의 개수 저장)
total := 0 (행렬 전체 1의 개수)
i := 0부터 n-1까지 반복:
j := 0부터 m-1까지 반복:
row[i] := row[i] + matrix[i][j]
col[j] := col[j] + matrix[i][j]
total := total + matrix[i][j]
다시 i := 0부터 n-1까지 반복:
j := 0부터 m-1까지 반복:
cand := total - row[i] - col[j] + ((m - row[i]) + (n - col[j]))
만약 matrix[i][j]가 0이 아니라면:
cand := cand + 2
그렇지 않으면:
cand := cand - 2
ret := ret와 cand 중 더 큰 값
ret 반환
왜 ±2 보정이 필요한가?
공식 total - row[i] - col[j] + (m - row[i]) + (n - col[j])은 행 i와 열 j에 속한 모든 셀이 한 번씩 뒤집힌다고 가정하고 값을 계산합니다. 하지만 교차점 셀 (i, j)는 실제로는 두 번 뒤집혀 원래 값이 유지되므로, 이중으로 계산된 효과를 상쇄해야 합니다.
matrix[i][j]가 1이라면, 공식에서 이 셀이 2번 제거된 것으로 잘못 반영되었으므로 +2로 보정합니다.
matrix[i][j]가 0이라면, 반대로 -2로 보정합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<vector<int>> &matrix) {
int n = matrix.size();
int m = matrix[0].size();
int ret = 0;
vector<int> row(n);
vector<int> col(m);
int total = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
row[i] += matrix[i][j];
col[j] += matrix[i][j];
total += matrix[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int cand = total - row[i] - col[j] + (m - row[i]) + (n -
col[j]);
if (matrix[i][j]) {
cand += 2;
}else {
cand -= 2;
}
ret = max(ret, cand);
}
}
return ret;
}
};
main() {
Solution ob;
vector<vector<int>> v = {{1,0,1},{0,1,0},{1,0,0}};
cout << (ob.solve(v));
}입력
{{1,0,1},{0,1,0},{1,0,0}}출력
8
복잡도 분석
시간 복잡도: O(n × m) — 행렬을 두 번 순회하므로 행렬 크기에 비례합니다.
공간 복잡도: O(n + m) — 각 행과 열의 합을 저장하는 배열이 필요합니다.
이처럼 행·열별 누적 합과 교차점 보정 기법을 활용하면, 모든 조합을 일일이 뒤집어 보지 않고도 최적의 결과를 빠르게 구할 수 있습니다.