[백준][C++] 14725 개미굴

 

 

 

알고리즘 종류

    - 문자열

    - 트라이(Trie)

 

 

 

사고 과정

    - 보아하니 트리를 구현하여 문자열을 저장하면 될 것 같았다. 이진트리만 만들어 봤지 어떻게 만들지 고민했다. 트리 종류를 찾아보니 트라이(Trie)라는 것이 문자열을 저장하는데 효과적인 자료구조라는 것을 알게 되었다. 트라이를 이용해서 해결하는 문제였다. 

    - 트라이를 공부할 필요성이 생겼다. 여기에 적어보았다.

 

    - 입력된 문자열을 vector에 담아 주고, vector를 이용해서 트리를 만들어 준다.

    - 완성된 트리에서 DFS를 실행하여 출력하면 알파벳 순으로 출력됩니다. map는 key를 기준으로 오름차순 정렬을 자동으로 합니다. 따라서, key는 string이므로 알파벳 순으로 자동 정렬됩니다.

 

 

 

구현(C++)

#include <vector>
#include <iostream>
#include <string>
#include <map>
 
using namespace std;
 
 
struct Node {
    map<string, Node> child;
};
 
 
 
void insert(Node &p, vector<string> v, int idx) {
    // idx는 string을 담은 vector에서의 현재 위치입니다.
    // idx가 vector의 끝에 도달하면 끝냅니다.
    if (idx == v.size()) return;
 
    // vector에서 가져온 string이 트리에 있는지 count()로 확인합니다.
    // 없으면, 0이 나옵니다. 따라서 key를 string으로 하는 node를 만들어 줍니다.
    if (!p.child.count(v[idx]))
        p.child[v[idx]] = Node();
 
    // 노드를 타고 들어갑니다.
    insert(p.child[v[idx]], v, idx + 1);
}
 
 
void print(Node &p, int depth = 0) {
    // 어느 깊이에 있는 모든 노드들을 가져옵니다.
    for (auto node : p.child) {
        for (int i = 0; i<depth; i++) {
            cout << "--";
        }
        cout << node.first << endl;
 
        // DFS이므로 깊이 순으로 타고 들어갑니다.
        print(node.second, depth + 1);
    }
 
}
 
 
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    Node root;
 
    int n;
    cin >> n;
 
    for (int i = 0; i<n; i++) {
        int k;
        cin >> k;
 
        vector<string> v(k);
 
        for (int j = 0; j<k; j++) {
            cin >> v[j];
        }
        insert(root, v, 0);
    }
 
    print(root);
 
}
 
 

 

 

 

시행착오

    - 이렇게 문자열 자료구조를 하나 더 배우게 되었습니다.

    - 포인터 사용법을 잊어버려서 고생 좀 했습니다.