문제 소개
이진 행렬(binary matrix)이 주어졌을 때, 행렬 내에서 서로 간의 비트 차이(bit difference)가 가장 큰 두 행의 쌍을 찾아야 합니다.
예를 들어 아래와 같은 행렬이 입력으로 주어진다면, 2번째 행과 3번째 행 사이의 비트 차이가 4로 가장 크기 때문에 출력은 [2, 3]이 됩니다.
접근 방법: 트라이(Trie) 활용
이 문제는 트라이(Trie) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 각 행을 이진 경로처럼 트라이에 삽입한 뒤, 현재 행과 가장 유사한 경로 또는 가장 다른 경로를 탐색하는 방식입니다.
해결 과정은 다음과 같습니다:
- 값(leaf)과 두 개의 자식 노드(child[0], child[1])를 가지는 트라이 구조체를 정의합니다.
- get_max_bit_diff() 함수를 정의합니다. 이 함수는 트라이의 루트, 행렬, 열의 개수(n), 행 인덱스(row_index)를 매개변수로 받습니다.
- temp := root, count := 0으로 초기화합니다.
- i := 0부터 i < n까지 반복합니다:
- temp의 child[matrix[row_index][i]]가 NULL이 아니면 → temp를 해당 자식 노드로 이동합니다.
- 그렇지 않고 child[1 - matrix[row_index][i]]가 NULL이 아니면 → temp를 반대 방향 자식 노드로 이동하고 count를 1 증가시킵니다.
- leaf_index := temp의 leaf 값을 저장합니다.
- temp_count := 0, temp := root로 다시 초기화합니다.
- i := 0부터 i < n까지 반복합니다:
- temp의 child[1 - matrix[row_index][i]]가 NULL이 아니면 → temp를 반대 방향 자식 노드로 이동하고 temp_count를 1 증가시킵니다.
- 그렇지 않고 child[matrix[row_index][i]]가 NULL이 아니면 → temp를 해당 자식 노드로 이동합니다.
- P = temp_count > count이면 (temp_count, temp의 leaf) 쌍을, 그렇지 않으면 (count, leaf_index) 쌍으로 설정합니다.
- P를 반환합니다.
메인 함수의 처리 흐름
- root = 새로운 TrieNode를 생성합니다.
- 0번째 행을 root에 삽입합니다.
- max_bit_diff := -무한대(INT_MIN)로 초기화합니다.
- pr과 temp라는 두 개의 pair를 선언합니다.
- i := 1부터 i < n까지 반복합니다:
- temp := get_max_bit_diff(root, mat, m, i)를 호출합니다.
- max_bit_diff < temp.first이면:
- max_bit_diff := temp.first로 갱신합니다.
- pr := (temp.second, i + 1) 쌍을 생성합니다.
- i번째 행을 root에 삽입합니다.
- 최종적으로 pr 쌍을 출력합니다.
C++ 구현 예제
아래 구현을 통해 더 잘 이해할 수 있습니다:
#include<bits/stdc++.h>
using namespace std;
const int MAX = 100;
class TrieNode {
public:
int leaf;
TrieNode *child[2];
TrieNode(){
leaf = 0;
child[0] = child[1] = NULL;
}
};
void insert(TrieNode *root, int matrix[][MAX], int n, int row_index){
TrieNode * temp = root;
for (int i=0; i<n; i++) {
if(temp->child[ matrix[row_index][i] ] == NULL)
temp->child[ matrix[row_index][i] ] = new TrieNode();
temp = temp->child[ matrix[row_index][i] ];
}
temp->leaf = row_index +1 ;
}
pair<int, int> get_max_bit_diff(TrieNode * root, int matrix[][MAX], int n, int row_index) {
TrieNode * temp = root;
int count = 0;
for (int i= 0 ; i < n ; i++) {
if (temp->child[ matrix[row_index][i] ] != NULL)
temp = temp->child[ matrix[row_index][i] ];
else if (temp->child[1 - matrix[row_index][i]] != NULL) {
temp = temp->child[1- matrix[row_index][i]];
count++;
}
}
int leaf_index = temp->leaf;
int temp_count = 0 ;
temp = root;
for (int i= 0 ; i < n ; i++) {
if (temp->child[ 1 - matrix[row_index][i] ] !=NULL) {
temp = temp->child[ 1- matrix[row_index][i] ];
temp_count++;
}
else if (temp->child[ matrix[row_index][i] ] != NULL)
temp = temp->child[ matrix[row_index][i] ];
}
pair <int ,int> P = temp_count > count ? make_pair(temp_count, temp->leaf): make_pair(count, leaf_index);
return P;
}
void get_max_diff( int mat[][MAX], int n, int m) {
TrieNode * root = new TrieNode();
insert(root, mat, m, 0);
int max_bit_diff = INT_MIN;
pair<int ,int> pr, temp ;
for (int i = 1 ; i < n; i++) {
temp = get_max_bit_diff(root, mat, m ,i);
if (max_bit_diff < temp.first ) {
max_bit_diff = temp.first;
pr = make_pair( temp.second, i+1);
}
insert(root, mat, m, i );
}
cout << "(" << pr.first <<", "<< pr.second << ")";
}
int main() {
int mat[][MAX] = {
{1 ,1 ,1 ,1 },
{1, 0, 1 ,1},
{0 ,1 ,0 ,0},
{1 ,0 ,0 ,0}
};
get_max_diff(mat, 4, 4) ;
}입력
{{1 ,1 ,1 ,1 },
{1, 0, 1 ,1},
{0 ,1 ,0 ,0},
{1 ,0 ,0 ,0}}, 4,4출력
(2,3)
결과 분석
위 예제에서 2번째 행 {1, 0, 1, 1}과 3번째 행 {0, 1, 0, 0}은 네 개의 비트가 모두 서로 달라 비트 차이가 4로 전체 행렬에서 가장 큽니다. 따라서 프로그램은 (2, 3)을 출력합니다.
모든 행 쌍을 일일이 비교하는 브루트 포스 방식은 O(n² × m)의 시간이 걸리지만, 트라이를 활용하면 각 행마다 한 번의 경로 탐색만으로 후보를 찾을 수 있어 대규모 행렬에서도 효율적인 성능을 기대할 수 있습니다.