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

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

6073번: Secret Message

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

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int m, n;
vector<int> 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<int>& 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<int>& 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<int> 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<int> 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] << "\n";
	}


	return 0;
}