C++ 이진 행렬에서 중복 행 찾기: 트라이(Trie)로 효율적으로 구현하기

이진 행렬(binary matrix)이 주어졌을 때, 그 안에 숨어 있는 중복 행을 찾는 방법을 알아봅니다. 예를 들어 다음과 같은 6×6 크기의 이진 행렬이 있다고 가정해 보겠습니다.

위 행렬에서는 3번, 4번, 5번 위치(인덱스는 0부터 시작)의 행이 각각 앞서 등장한 행과 완전히 동일합니다. 즉, 0번 행과 3번 행이 같고, 1번·4번·5번 행이 서로 중복됩니다.

트라이(Trie)를 활용한 해결 아이디어

이 문제는 트라이(Trie) 자료구조를 사용하면 매우 효율적으로 해결할 수 있습니다. 트라이는 표현해야 할 문자 종류가 적은 데이터를 저장하고 검색하는 데 최적화된 트리 형태의 구조로, 탐색 시간 복잡도가 키(key)의 길이에 비례하기 때문에 이론상 최적의 성능을 냅니다.

핵심 동작 방식은 다음과 같습니다.

• 각 행을 0과 1로 이루어진 하나의 키로 보고, 행 순서대로 트라이에 삽입합니다.
• 삽입하려는 행의 경로가 이미 존재하고 끝 노드(리프 노드)까지 도달한다면, 그 행은 이전에 등장한 적 있는 중복 행입니다.
• 중복으로 판별되면 해당 행의 인덱스를 화면에 출력합니다.

모든 행을 서로 일일이 비교하는 단순 방식(O(M²×N))과 달리, 트라이를 활용하면 전체 시간 복잡도를 O(M×N)까지 줄일 수 있습니다.

C++ 구현 예제

#include<iostream>
using namespace std;
const int MAX = 100;
class Trie {
    public:
    bool leaf_node;
    Trie* children[2];
};
Trie* getNode() {
    Trie* node = new Trie;
    node->children[0] = node->children[1] = NULL;
    node->leaf_node = false;
    return node;
}
bool insert(Trie*& head, bool* arr, int N) {
    Trie* curr = head;
    for (int i = 0; i < N; i++) {
        if (curr->children[arr[i]] == NULL)
        curr->children[arr[i]] = getNode();
        curr = curr->children[arr[i]];
    }
    if (curr->leaf_node)
    return false;
    return (curr->leaf_node = true);
}
void displayDuplicateRows(bool matrix[][MAX], int M, int N) {
    Trie* head = getNode();
    for (int i = 0; i < M; i++)
    if (!insert(head, matrix[i], N))
    cout << "There is a duplicate row at position: "<< i << endl;
}
int main() {
    bool mat[][MAX] = {
        {1, 1, 0, 1, 0, 1},
        {0, 0, 1, 0, 0, 1},
        {1, 0, 1, 1, 0, 0},
        {1, 1, 0, 1, 0, 1},
        {0, 0, 1, 0, 0, 1},
        {0, 0, 1, 0, 0, 1},
    };
    displayDuplicateRows(mat, 6, 6);
}

실행 결과

There is a duplicate row at position: 3
There is a duplicate row at position: 4
There is a duplicate row at position: 5

실행 결과를 통해 프로그램이 3번, 4번, 5번 위치의 중복 행을 정확하게 찾아낸 것을 확인할 수 있습니다.

코드 핵심 요약

• Trie 클래스 : 각 노드는 0과 1에 해당하는 두 개의 자식 포인터(children[2])와 리프 노드 여부(leaf_node)를 가집니다.
• getNode() : 새로운 트라이 노드를 생성하고 초기값(false)으로 설정합니다.
• insert() : 한 행을 트라이에 삽입합니다. 삽입을 마쳤을 때 해당 노드가 이미 리프 노드였다면 false를 반환하여 중복임을 알립니다.
• displayDuplicateRows() : 모든 행을 순회하면서 insert()의 반환값을 확인하고, 중복 행의 위치를 출력합니다.

마무리

트라이 대신 각 행을 문자열로 변환한 뒤 unordered_set(해시 집합)에 저장하며 중복을 검사하는 방법도 사용할 수 있습니다. 다만 트라이는 공통 접두어를 노드 단위로 공유하기 때문에 유사한 패턴이 많은 데이터에서 메모리 측면에서 유리하며, 이진 행렬처럼 문자 종류가 0과 1 두 가지뿐인 경우 특히 잘 어울리는 기법입니다.