이번 글에서는 흥미로운 부울 행렬(Boolean Matrix) 문제를 다뤄보겠습니다. 0과 1로만 구성된 부울 행렬이 주어졌을 때, 1이 표시된 위치를 찾아 해당 행과 열 전체를 모두 1로 변경하는 것이 목표입니다.
예를 들어 행렬의 mat[i][j] 위치에 1이 있다면, i번째 행의 모든 요소와 j번째 열의 모든 요소를 1로 만들어야 합니다.
문제 이해하기
다음과 같은 4x4 행렬이 주어졌다고 가정해 봅시다.
1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0
이 행렬에서 1은 (0,0), (0,3), (3,1) 세 곳에 있습니다. 따라서 0번째 행과 3번째 행 전체, 그리고 0번째 열, 1번째 열, 3번째 열 전체를 1로 채워야 합니다. 수정 후의 행렬은 다음과 같습니다.
1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1
알고리즘
matrixUpdate(matrix[R][C])
begin
크기 R인 배열 row[]와 크기 C인 배열 col[]을 정의하고 모두 0으로 초기화한다.
mat[R][C]를 순회하면서 1이 있는 위치의 행 인덱스는 row[], 열 인덱스는 col[]에 표시한다.
row[]와 col[]를 확인하여 표시된 행과 열의 모든 요소를 1로 채운다.
end
핵심 아이디어는 원본 행렬을 직접 수정하는 대신, 보조 배열(row, col)을 활용해 1이 존재하는 행과 열의 정보를 먼저 기록하는 것입니다. 이렇게 하면 순회 중에 값이 변경되어 생기는 오류를 방지할 수 있습니다.
C++ 코드 예제
#include <iostream>
#define R 4
#define C 4
using namespace std;
void updateMatrix(bool mat[R][C]) {
bool row[R];
bool col[C];
int i, j;
for (i = 0; i < R; i++) { // row 배열의 모든 요소를 0으로 초기화
row[i] = 0;
}
for (i = 0; i < C; i++) { // col 배열의 모든 요소를 0으로 초기화
col[i] = 0;
}
for (i = 0; i < R; i++) { // 1이 있는 위치를 row, col 배열에 표시
for (j = 0; j < C; j++) {
if (mat[i][j] == 1) {
row[i] = 1;
col[j] = 1;
}
}
}
for (i = 0; i < R; i++) { // 표시된 행과 열의 모든 요소를 1로 설정
for (j = 0; j < C; j++) {
if (row[i] == 1 || col[j] == 1) {
mat[i][j] = 1;
}
}
}
}
void displayMatrix(bool mat[R][C]) {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cout << mat[i][j];
}
cout << endl;
}
}
main() {
bool mat[R][C] = { {1, 0, 0, 1},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 1, 0, 0}
};
cout << "Given Matrix" << endl;
displayMatrix(mat);
updateMatrix(mat);
cout << "Updated Matrix" << endl;
displayMatrix(mat);
}
실행 결과
Given Matrix 1001 0000 0000 0100 Updated Matrix 1111 1101 1101 1111
복잡도 분석
시간 복잡도: 행렬을 총 세 번 순회하므로 O(R × C)입니다. 행렬의 크기에 비례하여 수행 시간이 증가합니다.
공간 복잡도: 행 정보를 저장하는 배열 R개와 열 정보를 저장하는 배열 C개가 필요하므로 O(R + C)입니다.
이처럼 보조 배열을 사용하는 방식은 구현이 간단하고 직관적이어서, 면접이나 코딩 테스트에서 자주 등장하는 대표적인 행렬 변형 문제 유형입니다.