백준 BOJ 14725 개미굴

Trie의 자료구조를 참고하고 map을 잘 사용하면 쉽게 풀린다고 한다.

 

어떻게 접근해야할지 감이 안잡혔는데 풀이를 익혀놔야겠따.

 

 

#include <iostream>
#include <memory.h>
#include <string>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <unordered_map>
#include <map>
#define M 1e7+19
using namespace std;
using lld = long long int;
using pii = pair<int, int>;
int n,m;
 
vector<string> v[1000];
 
struct Node {
    map<string, Node> child;
};
 
void insert(Node &node, vector<string> &a, int idx) {
    if (idx == a.size()) return;
    string cur = a[idx];
    if (node.child.count(cur) == 0) node.child[cur] = Node();
    
    insert(node.child[cur], a, idx + 1);
}
 
void dfs(Node &node, int dep) {
    for (auto i : node.child) {
        for (int j = 0;j < dep;j++) cout << "--";
        cout << i.first << "\n";
        dfs(i.second, dep + 1);
    }
}
 
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    for (int i = 0;i < n;i++) {
        int x; cin >> x;
        for (int j = 0;j < x;j++) {
            string s; cin >> s;
            v[i].push_back(s);
        }
    }
 
    Node root;
 
    for (int i = 0;i < n;i++) {
        insert(root, v[i], 0);
    }
 
    dfs(root, 0);
 
    return 0;
}

 

for (std::map<char,int>::iterator it=mymap.begin(); it!=mymap.end(); ++it)
    std::cout << it->first << " => " << it->second << '\n';

  return 0;
}



// 여기선 trie[node].child가 map
for (auto [s, idx] : trie[node].child) {
			cout << string(2 * depth, '-') << s << '\n';
			sol(idx, depth + 1);
		}


// 여기선 child가 map
for(auto i : v.child){
		for(int j=0; j<dep; j++) cout << "--";
		cout << i.first << "\n";
		dfs(i.second, dep+1);
	}

iterator로 map의 key에 접근하는 방법은 가장 위와 같고

다른 사람들의 코드를 보면서 map에 어떻게 접근하는지 보니 

auto를 이용하여 위와 같이 접근하였다.

 

In C++11:

• std::set, std::multiset, std::map and std::multimap are guaranteed to be ordered according to the keys (and the criterion supplied)
• in std::multiset and std::multimap, the Standard imposes that equivalent elements (those which compare equal) are ordered according to their insertion order (first inserted first)
• std::unordered_* containers are, as the name imply, not ordered. Most notably, the order of elements may change when the container is modified (upon insertion/deletion).

--> map은 key에 대해 순서 보장. unordered_map는 보장 x

 

 

-------

구조체() 는 생성자를 의미한다

예를들어 struct Node{..}; 의   Node n = Node();  자료형을 선언하면서 초기화 하고싶을떄? 

혹은 map<string,Node> m;   m["str"] = Node(); 와 같이 사용할 수 있다.