boj 14725 개미굴

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

14725번: 개미굴

개미굴의 각 저장소들을 트라이 방식으로 저장할 수 있습니다.

A B C 이런식으로 입력이 들어오면 A 다음 B 다음 C 이런식으로 저장하는 방식입니다.

 

다만 들어오는 데이터가 문자열 방식이므로 일반적인 배열로는 할 수 없으며 map를 사용합니다.

m.find(str) 메소드를 이용하여 해당 depth에 문자열이 저장되었는지 확인 후

저장되었다면 다음 depth로 이동, 저장되지 않았다면 해당 depth의 map에 문자열을 저장 후 다음 depth로 이동합니다.

 

출력은 개미굴의 구조를 사전 순으로 출력합니다.

map은 이미 정렬이 된 자료구조이므로 iterator를 이용하여 사전 순으로 출력해줍니다.

 

 

#include <iostream>
#include <map>
#include <string>
#define MAX 16
using namespace std;
 
string list[MAX];
int N, M;
 
typedef struct Trie {
    map<string, Trie*> m;
 
    ~Trie() {
        map<string, Trie*>::iterator iter = m.begin();
        for (; iter != m.end(); iter++) {
            delete (*iter).second;
        }
    }
 
    void insert(int idx) {
        if (idx == M) return;
 
        if (m.find(list[idx]) == m.end()) {
            m.insert({ list[idx], new Trie() });
            m[list[idx]]->insert(idx + 1);
        }
        else {
            m[list[idx]]->insert(idx + 1);
        }
    }
 
    void find(int depth) {
        map<string, Trie*>::iterator iter = m.begin();
        for (; iter != m.end(); iter++) {
            for (int i = 0; i < depth; i++) {
                cout << "--";
            }
            cout << (*iter).first << '\n';
 
            (*iter).second->find(depth + 1);
        }
    }
}Trie;
 
Trie *t;
 
void func() {
    t->find(0);
}
 
void init() {
    t = new Trie();
}
 
void input() {
    init();
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> M;
        for (int j = 0; j < M; j++) {
            cin >> list[j];
        }
        t->insert(0);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}