부울 행렬(Boolean Matrix)은 오직 0과 1 두 가지 값만으로 구성된 행렬입니다. 이 문제에서는 크기가 m×n인 부울 행렬 arr[m][n]이 주어지며, 다음 조건에 따라 행렬을 수정해야 합니다.
문제 정의
만약 m[i][j] = 1이라면, i번째 행의 모든 요소와 j번째 열의 모든 요소를 1로 변경해야 합니다. 즉, 값이 1인 원소가 하나라도 있으면 해당 원소가 속한 행과 열 전체가 1로 채워집니다.
예시
입력: arr[2][2] = 1 0 0 0 출력: arr[2][2] = 1 1 1 0
설명: arr[0][0] = 1이므로 arr[0][0] = arr[0][1] = 1이 되고, 동시에 arr[0][0] = arr[1][0] = 1이 됩니다. 결과적으로 0번째 행 전체와 0번째 열 전체가 1로 바뀌게 됩니다.
알고리즘 접근 방법
이 문제는 두 개의 플래그 변수(row_flag, col_flag)를 활용하여 해결할 수 있습니다. 각 플래그는 첫 번째 행과 첫 번째 열을 1로 변경해야 하는지 여부를 기록합니다. 핵심 아이디어는 다음과 같습니다.
- 첫 번째 행과 열을 마커로 활용: 어떤 원소 mat[i][j]가 1이면, mat[0][j]와 mat[i][0]을 1로 설정하여 "i번째 행"과 "j번째 열"을 1로 만들어야 한다는 정보를 행렬 자체에 저장합니다.
- 플래그 기록: 순회 중 첫 번째 행에서 1을 발견하면
row_flag를, 첫 번째 열에서 1을 발견하면col_flag를 1로 설정합니다. 첫 번째 행/열은 마커로 덮어써질 수 있으므로 원래 상태를 미리 기록해 두는 것입니다. - 내부 원소 갱신: 마커 설정이 끝나면, 첫 번째 행 또는 첫 번째 열의 값이 1인 경우 해당 위치의 원소를 1로 변경합니다.
- 플래그 처리: 마지막으로 플래그 값에 따라 첫 번째 행과 첫 번째 열 전체를 1로 채웁니다.
이 방식은 별도의 추가 배열 없이 주어진 행렬 안에서 정보를 저장하므로 O(1)의 추가 공간만 사용한다는 큰 장점이 있습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
const int R = 3;
#define C 4
// 조건에 맞게 행렬의 행과 열을 1로 변경하는 함수
void matrixflip(int mat[R][C]) {
int row_flag = 0; // 첫 번째 행을 1로 만들어야 하는지 표시
int col_flag = 0; // 첫 번째 열을 1로 만들어야 하는지 표시
// 1단계: 첫 번째 행/열을 마커로 활용
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (i == 0 && mat[i][j] == 1)
row_flag = 1;
if (j == 0 && mat[i][j] == 1)
col_flag = 1;
if (mat[i][j] == 1) {
mat[0][j] = 1; // j번째 열을 1로 표시
mat[i][0] = 1; // i번째 행을 1로 표시
}
}
}
// 2단계: 마커 값을 기준으로 내부 원소 갱신
for (int i = 1; i < R; i++) {
for (int j = 1; j < C; j++) {
if (mat[0][j] == 1 || mat[i][0] == 1) {
mat[i][j] = 1;
}
}
}
// 3단계: 플래그에 따라 첫 번째 행/열 처리
if (row_flag) {
for (int i = 0; i < C; i++) {
mat[0][i] = 1;
}
}
if (col_flag) {
for (int i = 0; i < R; i++) {
mat[i][0] = 1;
}
}
}
int main() {
int mat[R][C] = { { 1, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 1, 0 } };
cout << "Input Matrix :\n";
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cout << mat[i][j] << " ";
}
cout << endl;
}
matrixflip(mat);
cout << "Matrix after bit flip :\n";
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cout << mat[i][j] << " ";
}
cout << endl;
}
return 0;
}실행 결과
Input Matrix : 1 0 0 0 0 0 0 0 0 0 1 0 Matrix after bit flip : 1 1 1 1 1 0 1 0 1 1 1 1
복잡도 분석
- 시간 복잡도: O(m × n) — 행렬의 모든 원소를 단계별로 순회합니다.
- 공간 복잡도: O(1) — 추가 배열 없이 행렬 자체를 마커로 활용하므로 상수 크기의 변수만 사용합니다.