[ BOJ 백준 6073번 - Secret Message ] 해설 및 코드

https://www.acmicpc.net/problem/6073

 

목적

코드단어(codeword)가 m개의 가로챈 코드(intercepted code)중 몇 개와 앞부분(initial bits)이 일치하는지 구하라. 

 

 

접근법

1. 트라이 자료구조를 이용하여 접근한다. 아래 그림은 예제로 주어진 4개의 가로챈 코드로 구성한 트라이 구조의 형태이다.

 

 

 

2. 각 노드는 몇 개의 가로챈 코드에 사용되었는지, 가로챈 코드의 끝부분인지에 대한 정보를 담고 있어야 한다. 나타내자면 다음과 같다.

 

 

 

 

 

3. 이와 같은 정보를 가지고 코드단어와 앞부분(initial bits)이 일치하는 것이 몇 개나 되는지 계산한다. 가로챈 코드는 중복되는 데이터가 존재한다. 때문에 소스코드를 보면 알 수 있듯이 end의 자료형을 bool이 아닌 int로 하여, 증가 연산자로 값을 갱신함을 알 수 있다. 

 

4. 트라이 구조체를 동적할당 시에 new 연산자를 사용하는데, 컴파일러에 따라 구조체를 다르게 초기화한다. 일반적으로 new trie()와 같이 괄호를 붙여주면 0으로 초기화 된다.

 

#include<iostream>
 
using namespace std;
 
struct trie {
    trie* next[2];
    int cnt,end;
}root;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int m, n; cin >> m >> n;
    
    while (m--) {
        int k; cin >> k;
        // insert
        trie* node = &root;
        while(k--) {
            int bit; cin >> bit;
            if (node->next[bit]==NULL)node->next[bit] = new trie;
            node = node->next[bit];
            ++node->cnt;
        }
        ++node->end;
    }
    
    while(n--) {
        int cnt = 0;
        int k; cin >> k;
        //search
        trie* node = &root;
        while (k--) {
            int bit; cin >> bit;
            if (node==NULL)continue;
 
            cnt += node->end;
            node = node->next[bit];
        }
        if (node!=NULL) cnt += node->cnt;
 
        cout << cnt << '\n';
    }
}

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.