[C++] 14725번 개미굴 - 자료 구조, 문자열, 트리, 트라이

1. 문제
   • 문자열간 간선 정보를 알려줄 때 트리를 구성하고 사전 순서가 앞서도록 DFS를 한 결과를 출력하라.
   • 정점의 개수 n(1<=n<=1000), 간선의 개수 k(1<=k<=15)
2. 구현 방법
   • 트라이를 사용하자.

 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <map>
#include <vector>

using namespace std;

struct TrieNode {
    map<string, TrieNode*> children;
    
    void insert(vector<string> v, int idx) {
        if(idx == v.size())
            return;
        map<string, TrieNode*>::iterator iter = children.find(v[idx]);
        if(iter != children.end())
            iter->second->insert(v, idx+1);
        else {
            TrieNode* n = new TrieNode;
            children.insert({v[idx], n});
            n->insert(v, idx+1);
        }
    }
    
    void print(int idx) {
        if(children.empty()) return;
        for(auto iter = children.begin(); iter != children.end(); iter++) {
            for(int i=0; i<idx; i++)
                cout << "--";
            cout << iter->first << '\n';
            iter->second->print(idx+1);
        }
    }
};

int n;

TrieNode* root = new TrieNode;

void input()
{
    cin >> n;
    
    for(int i=0; i<n; i++) {
        int 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 main()
{
    cin.sync_with_stdio(0);
    
    input();
    
    root->print(0);
    
    return 0;
}

트라이를 종만북에 있는데로 구성하고 이를 이용해 문제를 풀려고 하니 잘 되지 않았다. 노드 하나에 문자를 넣으면 단어와 단어 사이를 구별하는 것이 어려웠다. 이렇게 딱 틀을 닫고 보니 문제를 전혀 풀 수 없었던 것이다.

 

다른 사람이 짠 코드를 보고 나서야 map으로 문자열이 들어간 트라이를 구현할 수 있다는 것을 알게 되었고 이를 토대로 문제를 해결할 수 있었다.

 

참고한 사이트는 아래에 있다.

https://allmymight.tistory.com/81

[백준] 14725번 개미굴 - C/C++

 

 

 

 

 

 

 

 

 

 

 

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.