(14725) 개미굴

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

단계별로 풀어보기

46단계(문자열 알고리즘 1) 3번째

 

 

 

트라이 연습용 문제. 트라이를 쓸 줄 알기 위해서는 포인터 변수에 대해 알아야 한다. 많이 알 필요도 없다. 간단하게만 알면 노드에서 노드로 이어지는 형태를 구조체로 쉽게 구현할 수 있다.

 

 

 

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

struct Node{
  map<string, Node*> next;
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  Node* root= new Node();
  
  cin >> n;
  
  while(n--){
    int k;
    
    cin >> k;
    
    Node* now= root;
    
    while(k--){
      string t;
      
      cin >> t;
      
      if(now->next[t]==nullptr)  now->next[t]= new Node();
      
      now= now->next[t];
    }
  }
  
  auto preorder= [&](auto self, Node* now, int depth) -> void {
    for(auto iter:now->next){
      for(int i=0;i<depth;i++)  cout << "--";
      cout << iter.first << "\n";
      
      self(self, iter.second, depth+1);
    }
  };
  
  preorder(preorder, root, 0);
  
  return 0;
}