[BOJ] 14725번 | 개미굴 (C++)

🔗문제 보러가기

14725번: 개미굴

 

👨‍💻풀이 과정

 

출처 : 메이플스토리 위키 - 개미굴 1

 

메이플스토리 개미굴이 생각나는 문제였습니다. 트라이(Trie) 자료구조를 활용해서 풀 수 있었는데, 트라이와 관련된 코드를 작성하는 게 익숙하지 않아 조금 오래 걸렸습니다. 같은 층에 여러 개의 방이 있을 경우에는 사전순으로 먹이 정보를 출력해야 하기에 map을 활용하여 트라이를 구현하였습니다.

class Trie
{
public:
    Trie(int depth) : depth(depth) { }
    ~Trie();
    void Insert(const vector<string>& foodNames, int index);
    void Show();

private:
    int depth;
    map<string, Trie*> foods;
};

 

동적 할당으로 트라이 객체를 생성해줄 것이기 때문에, 소멸자에서 메모리 해제 코드를 작성해줍니다.

Trie::~Trie()
{
    for (auto& food : foods)
        if (food.second != nullptr)
            delete food.second;
}

 

로봇 개미가 방에 들어간 순서대로 입력을 주기 때문에, 이를 배열에 받아서 재귀 형태로 트라이에 넣는 방식으로 구현하였습니다.

void Trie::Insert(const vector<string>& foodNames, int index)
{
    if (index >= foodNames.size())
        return;
    
    auto findIt = foods.find(foodNames[index]);
    if (findIt == foods.end())
    {
        Trie* newFood = new Trie(depth + 1);
        foods.insert(make_pair(foodNames[index], newFood));
        newFood->Insert(foodNames, index + 1);
        return;
    }

    Trie* nextFood = findIt->second;
    nextFood->Insert(foodNames, index + 1);
}

 

출력하는 코드 또한, 현재 깊이(depth) * 2에 해당하는 개수만큼 "-"을 먼저 출력해주고, DFS 방식으로 출력해주면 됩니다.

 

void Trie::Show()
{
    string line(2 * depth, '-');
    for (const auto& food : foods)
    {
        cout << line << food.first << "\n";
        food.second->Show();
    }
}

 

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;

class Trie
{
public:
    Trie(int depth) : depth(depth) { }
    ~Trie();
    void Insert(const vector<string>& foodNames, int index);
    void Show();

private:
    int depth;
    map<string, Trie*> foods;
};

Trie::~Trie()
{
    for (auto& food : foods)
        if (food.second != nullptr)
            delete food.second;
}

void Trie::Insert(const vector<string>& foodNames, int index)
{
    if (index >= foodNames.size())
        return;
    
    auto findIt = foods.find(foodNames[index]);
    if (findIt == foods.end())
    {
        Trie* newFood = new Trie(depth + 1);
        foods.insert(make_pair(foodNames[index], newFood));
        newFood->Insert(foodNames, index + 1);
        return;
    }

    Trie* nextFood = findIt->second;
    nextFood->Insert(foodNames, index + 1);
}

void Trie::Show()
{
    string line(2 * depth, '-');
    for (const auto& food : foods)
    {
        cout << line << food.first << "\n";
        food.second->Show();
    }
}

int main()
{
    ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
    int numOfData;
    cin >> numOfData;
    
    Trie* root = new Trie(0);

    while (numOfData--)
    {
        int N;
        cin >> N;

        vector<string> foods(N);
        for (int i = 0; i < N; i++) cin >> foods[i];

        root->Insert(foods, 0);
    }

    root->Show();
    delete root;
    return 0;
}