[백준/BOJ] 백준 6073번 : Secret Message

[백준/BOJ] 백준 6073번 : Secret Message

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

노드에 해당 노드에서 끝나는 것의 개수, 앞으로 더 나아가는 자식 노드의 개수, 비트(0,1)에 따른 자식 노드를 저장하는 정보를 담고 트라이를 만들어 문제를 해결했다.

코드

#include #include #include #include using namespace std; int m, n; vector output; struct node { int finish; int children_cnt; node* children[2]; //비트(0,1) }; node* Make_node() { node* ret = new node(); ret->finish = 0; ret->children_cnt = 0; for (int i = 0; i < 2; i++) { ret->children[i] = NULL; } return ret; } void Insert(node*& here, vector& input, int index) { if (index == input.size()) { here->finish++; return; } if (here->children[input[index]] != NULL) { here->children_cnt++; Insert(here->children[input[index]], input, index + 1); } else { here->children[input[index]] = Make_node(); here->children_cnt++; Insert(here->children[input[index]], input, index + 1); } } int Solve(node*& here, vector& check, int index) { if (index == check.size()) { return here->finish + here->children_cnt; //지금 끝난것의 개수 + 앞으로 더 이어지는게 있는 개수 } int ret; //앞으로 더 이어지는게 있을때 if (here->children[check[index]] != NULL) { ret = here->finish + Solve(here->children[check[index]], check, index + 1); } //앞으로 더 이어지는게 없을때 else { ret = here->finish; } return ret; } int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); cin >> m >> n; //트라이를 만든다 node* tree = Make_node(); for (int i = 0; i < m; i++) { int num; vector input; cin >> num; for (int j = 0; j < num; j++) { int this_input; cin >> this_input; input.push_back(this_input); } Insert(tree, input, 0); } for (int i = 0; i < n; i++) { int num; vector check; cin >> num; for (int j = 0; j < num; j++) { int this_check; cin >> this_check; check.push_back(this_check); } int result = Solve(tree, check, 0); output.push_back(result); } for (int i = 0; i < output.size(); i++) { cout << output[i] << "

"; } return 0; }

from http://geniusjo-story.tistory.com/490 by ccl(A) rewrite - 2021-08-31 14:00:30