백준 [14725] 개미굴

문제 설명

 

문제 링크 

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

14725번: 개미굴

풀이

trie를 이용하여 풀이할 수 있다.

trie를 구현할때 string을 인덱스로 하고 값은 Node구조체로 하기 위해 map을 이용한다.

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

struct Node {
    map<string, Node> child;
};

void insert(Node &node, vector<string> &arr, int idx = 0) {
    if (idx == arr.size()) return;
    if (!node.child.count(arr[idx])) node.child[arr[idx]] = Node();
    insert(node.child[arr[idx]], arr, idx + 1); 
}

void find(Node &node, int depth = 0) {
    for (auto nxt : node.child) {
        for (int i = 0; i < depth; i++) printf("--");
        cout << nxt.first << "\n";
        find(nxt.second, depth + 1);
    }
}

int main() {
    int N; scanf("%d", &N);
    Node root;
    while (N--) {
        int K; scanf("%d", &K);
        vector<string> v;
        while (K--) {
            string tmp; cin >> tmp;
            v.push_back(tmp);
        }
        insert(root, v);
    }
    find(root);
}