백준: Class 6 - 14725(Trie)

</br> 14725: 개미굴은 트라이를 사용하면 될 것 같은 문제다
트라이를 알기는 하는데 구현은 해 본 적이 없으므로, 정리하도록 하자
</br>

Trie 구현

vector<string> v;

struct Trie{
    bool fin;
    string val;
    map<string, Trie*> nodes;
    vector< pair<string, Trie*> > sortedNodes;
    Trie(string s){
        fin = false;
        val = s;
    }
};

현재가 끝인지 아닌지를 저장하는 bool fin, 현재 값을 저장하는 string val, 그리고 다음으로 연결되는 자식들 nodes로 만들었다.
개미굴은 정렬된 값이 필요하므로, 벡터 sortedNodes를 추가했다.

    void Tinsert(int i){
        if( nodes.count(v[i]) == 0 ) nodes[v[i]] = new Trie(v[i]);
        if( v.size()-1 == i ) fin = true;
        else nodes[v[i]]->Tinsert(i+1);
    }

값을 넣을 때, 일단 걔가 있는지 확인한다. 없다면 새 노드를 만들어서 추가해 준다.
만약 현재가 마지막 노드라면, fin임을 표시하고 끝낸다.
그게 아니면, 다음으로 넘기며 계속 넣어 준다.

    void Tsort(){
        sortedNodes = vector< pair<string, Trie*> >(nodes.begin(), nodes.end());
        sort(sortedNodes.begin(), sortedNodes.end());
    }
    void Tprint(int d){
        Tsort();
        for(int i = 0; i < sortedNodes.size(); i++){
            for(int j = 0; j < d; j++){
                cout << "--";
            }
            cout << sortedNodes[i].first << endl;
            sortedNodes[i].second->Tprint(d+1);
        }
    }

프린트할 때, 일단 맵을 벡터로 변환하고 정렬을 해준다.
그리고 현재 깊이 d에 따라 알맞게 출력해 준다.
</br>

14725: 개미굴

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

#include <bits/stdc++.h>

using namespace std;

vector<string> v;

struct Trie{
    bool fin;
    string val;
    map<string, Trie*> nodes;
    vector< pair<string, Trie*> > sortedNodes;
    Trie(string s){
        fin = false;
        val = s;
    }
    void Tinsert(int i){
        if( nodes.count(v[i]) == 0 ) nodes[v[i]] = new Trie(v[i]);
        if( v.size()-1 == i ) fin = true;
        else nodes[v[i]]->Tinsert(i+1);
    }
    void Tsort(){
        sortedNodes = vector< pair<string, Trie*> >(nodes.begin(), nodes.end());
        sort(sortedNodes.begin(), sortedNodes.end());
    }
    void Tprint(int d){
        Tsort();
        for(int i = 0; i < sortedNodes.size(); i++){
            for(int j = 0; j < d; j++){
                cout << "--";
            }
            cout << sortedNodes[i].first << endl;
            sortedNodes[i].second->Tprint(d+1);
        }
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    Trie trie = Trie("");

    for(int i = 0; i < n; i++){
        int k;
        cin >> k;
        v.clear();
        for(int i = 0; i < k; i++){
            string a;
            cin >> a;
            v.push_back(a);
        }
        trie.Tinsert(0);
    }

    trie.Tprint(0);

}

최종 코드는 이런 모양
</br>

---

처음 해 봤는데 재밌구나
</br>