[백준 14725][💛2] 개미굴 (트라이)

🚀 난이도

💛 골드 2

🚀 문제

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

🚀 내 풀이 ⭕

트라이에 관한 더 자세한 설명은 이 포스트를 참고해주세요. 👉 (C++) 문자열 집합 : 트라이 자료구조

• 1️⃣ 트라이 그래프(트리)를 만들어 그 안에 모든 문자열을 저장하면 위와 같은 모양이 된다.
• 2️⃣ 그리고 이를 DFS 로 탐색하며 출력하면 된다.

노드에 들어갈 데이터가 문자열(string)이기 때문에, 숫자 혹은 알파벳만 사용할 때와 다르게 자식 노드(다음 글자)들을 배열로 놓기는 힘들다. 배열처럼 임의 접근이 빠른 자료구조로는 맵이 있으니 배열 대신 사용할 수 있을 것이다. 그러나 문제에서 같은 깊이에 여러 방이 있을 땐 사전 순서가 앞서는 먹이를 먼저 탐색하라고 했기 때문에 해시맵이 아닌 정렬된 순서를 유지해주는 그냥 일반 map 을 사용하였다.

#include <bits/stdc++.h>

using namespace std;

class AntDen {
private:
    map<string, AntDen*> child; // key : 자식 문자열(다음 문자열)  valuse : 자식 객체 주소 

public:
    /* 트라이 트리 만들기 (재귀로 구현) */
    void Insert(vector<string>& foods, int index) {
        if (index == foods.size()) 
            return;

        if (child.find(foods[index]) == child.end())
            child[foods[index]] = new AntDen();
        child[foods[index]]->Insert(foods, index + 1);
    }

    void Output(int depth) { // DFS
        for (auto& ch : child) {
            for (int i = 0; i < depth; ++i) // 깊이 당 -- 한 번 
                cout << "--";
            cout << ch.first << '\n';
            ch.second->Output(depth + 1);
        }
    }
};

int main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;

    AntDen* root = new AntDen();
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        vector<string> foods(k);
        for (int j = 0; j < k; ++j)
            cin >> foods[j];

        root->Insert(foods, 0); // 트라이 트리 만들고
    }

    root->Output(0); // DFS 탐색
}

트라이를 만드는 Insert 함수는 재귀를 안쓰고 아래와 같이 반복문으로 구현할 수도 있다.

    void Insert(vector<string>& foods) {
        AntDen* now = this;
        for (int i = 0; i < foods.size(); ++i) {
            if (now->child[foods[i]] == nullptr)
                now->child[foods[i]] = new AntDen();
            now = now->child[foods[i]];
        }
    }

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기