백준 14725 개미굴 쉬운 풀이 (C++/CPP)

문제링크 : https://www.acmicpc.net/problem/14725

아이디어

• 계층구조 trie로 표현한다음
• 규칙에 맞도록 출력(DFS)
  • 출력할떄 알파벳순서로 어떻게 정렬하지?
  • child가 map 순서대로를 이용

시간복잡도 계산

• trie생성
  • 모든 입력에 대해 : O(N)
  • 모든 먹이개수에 대해 trie 생성: O(K)
  • 총합 : O(NK)
• trie 출력, DFS
  • DFS 출력 : O(V+E)
  • V : 노드개수 : NK
  • E : 노드간선개수 : NK
  • O(NK)
• 합 : O(NK) : 1.5e4

인트 계산

• 노드 인덱스 : 최대 NK

코드

#include <iostream>
#include <vector>
#include <map>
#include <string>
 
using namespace std;
 
struct node {
    bool fin;
    map<string, int> child;
    string cur;
    node(string s) {
        fin = false;
        cur = s;
        child.clear();
    }
};
 
vector<node> trie;
 
int insert(int nodi, string s) {
    
    if(trie[nodi].child[s] == 0) {
        trie[nodi].child[s] = trie.size();
        trie.push_back(s);
    }
    
    return trie[nodi].child[s];
}
 
void dfs(int cur, int depth) {
    if(cur != 0) {
        for(int i=0; i<depth-1; i++) cout << "--";
        cout << trie[cur].cur <<'\n';
    }
    for(auto it = trie[cur].child.begin(); it!=trie[cur].child.end(); it++) {
        dfs(it->second, depth+1);
    }
}
 
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N; cin >> N;
    
    trie.push_back(node(""));
    
    while(N--) {
        int en; cin >> en;
        int pre = 0;
        while(en--) {
            string es; cin >> es;
            pre = insert(pre, es);
        }
    }
    
    dfs(0,0);
    
    return 0;
}
 

문제유형

• TRIE - 여러글자
  • 일반 TRIE가 한글자씩 정보 저장
  • 여러글자를 가지고 TRIE
  • node의 child에 알파벳이나 숫자갯수만큼 저장하는 것이 아닌
  • map을 가지고 다음 노드를 관리