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

1. 문제

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

 

2. 알고리즘 분류

• 자료 구조
• 문자열
• 트리
• 트라이

 

3. 소스 코드

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

using namespace std;

int N, K;

struct Trie {
    map<string, Trie*> m;

    // 트라이 삽입 함수
    void insert(vector<string>& v, int idx) {
        // 삽입할 vector 인덱스 넘었을 경우, Return
        if (idx == v.size()) return;

        // 새 트라이 할당 및 추가
        if (m.find(v[idx]) == m.end()) {
            Trie* trie = new Trie;
            m.insert({ v[idx], trie });
        }

        // 다음 인덱스 삽입
        m[v[idx]]->insert(v, idx + 1);
    }

    // 트라이 내용 출력
    void print(int depth) {
        // 트라이 map 탐색
        for (auto& i : m) {
            // depth만큼 -- 출력
            for (int j = 0; j < depth; j++)
                cout << "--";
            
            // 트라이 값 출력
            cout << i.first << '\n';

            // 다음 트라이 탐색
            i.second->print(depth + 1);
            delete i.second;
        }
    }
};

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

    // 트라이 선언
    Trie* root = new Trie;

    // N : 먹이 정보의 개수
    cin >> N;

    for (int i = 0; i < N; i++) {
        // K : 로봇 개미 한마리가 보내준 먹이 정보 개수
        cin >> K;

        // 먹이 정보 입력
        vector<string> v;
        for (int j = 0; j < K; j++) {
            string str;
            cin >> str;
            v.push_back(str);
        }

        // 먹이 정보 삽입
        root->insert(v, 0);
    }
    int de = 1;
    // 먹이 정보 출력
    root->print(0);
    delete root;

    return 0;
}

 

4. 유용한 자료 구조

1) Trie(트라이)

1. 정의
 - 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료 구조
 
2. 활용
 1) 자동 완성 기능, 사전 검색 등 문자열을 탐색하는데 특화

struct Trie {
    bool finish; // 끝나는 지점을 표시해줌
    Trie* next[26]; // 26가지 알파벳에 대한 트라이

    // 생성자
    Trie() : finish(false) {
        memset(next, 0, sizeof(next));
    }

    // 소멸자
    ~Trie() {
        for (int i = 0; i < 26; i++)
            if (next[i])
                delete next[i];
    }

    // 트라이에 문자열 삽입
    void insert(const char* key) {
        if (*key == '\0')
            finish = true; // 문자열이 끝나는 지점일 경우 표시
        else {
            int curr = *key - 'A';
            if (next[curr] == NULL)
                next[curr] = new Trie(); // 탐색이 처음되는 지점일 경우 동적할당
            next[curr]->insert(key + 1); // 다음 문자 삽입
        }
    }

    // 트라이에서 문자열 찾기
    Trie* find(const char* key) {
        if (*key == '\0') return this; // 문자열이 끝나는 위치를 반환
        int curr = *key - 'A';
        if (next[curr] == NULL) return NULL; // 찾는 값이 존재하지 않음
        return next[curr]->find(key + 1); // 다음 문자를 탐색
    }
};
출처: https://eun-jeong.tistory.com/29 [흔들리며 피는 꽃:티스토리]