[백준] 5446 용량 부족

트라이 하다보니 재밌다 ㅋㅋㅋ

이 문제는 트라이를 그려보면 쉽다

먼저 트라이를 그릴 때 처음 입력받는 N개는 

지울 수 있는 변수 del을 true로 넣어준다

두번째로 입력받는 M개는

지울 수 없으므로 del = false로 놔준다

그럼 이제 트라이를 모두 돌아보며 지울 수 있는지 없는지 판단하자

지울 수 있는 조건은

1. del이 참일 때 지울 수 있따 이 때는 *를 쓴다고 생각해 return 해준다

2. del이 거짓이여도 단어의 끝부분이여서 vaild==true일 때 지울 수 있다

한번 쭉돌면 답이 나온다~

소스코드

#include <iostream>
using namespace std;
int ans;
char arr[22];
struct Trie {
    bool vaild, exist, del;
    Trie* node[128];
    Trie() : vaild(false), exist(false), del(false) {
        for (int i = 0; i < 128; i++) node[i] = 0;
    }
    ~Trie() {
        for (int i = 0; i < 128; i++)
            if (node[i]) delete node[i];
    }
    void add(const char* s,bool ok) {
        if (*s == 0) {
            del = ok;
            vaild = ok; return;
        }
        else {
            int pos = *s;
            if (node[pos] == NULL) node[pos] = new Trie();
            exist = true;
            del = ok;
            node[pos]->add(s + 1,ok);
        }
    }
    void dfs() {
        if (del) {
            ans++; return;
        }
        else if (vaild) ans++;
        for (int i = 0; i < 128; i++) {
            if (node[i]) node[i]->dfs();
        }
    }
};
int main() {
    int t, n, m; scanf(" %d", &t);
    while (t--) {
        scanf(" %d", &n);
        Trie* root = new Trie();
        for (int i = 0; i < n; i++) {
            scanf(" %s", &arr);
            root->add(arr, true);
        }
        scanf(" %d", &m);
        for (int i = 0; i < m; i++) {
            scanf(" %s", &arr);
            root->add(arr, false);
        }
        ans = 0;
        root->dfs();
        printf("%d\n", ans);
        delete root;
    }
}