[백준/BOJ] 백준 5052번 : 전화번호 목록

www.acmicpc.net/problem/5052

5052번: 전화번호 목록

트라이를 이용하여 문제를 해결하였다.

 

코드

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

int t;
int n;

struct node
{
	node* children[10];
	int children_num;
	bool finish;
};

node* Make_node()
{
	node* maked_node = new node();

	for (int i = 0; i < 10; i++)
		maked_node->children[i] = NULL;

	maked_node->children_num = 0;
	maked_node->finish = false;

	return maked_node;
}

void Insert(node* here, string input, int index)
{
	if (index == input.size())
	{
		here->finish = true;
		return;
	}

	if (here->children[input[index] - '0'] == NULL)
	{
		here->children_num++;
		here->children[input[index] - '0'] = Make_node();
		Insert(here->children[input[index] - '0'], input, index + 1);
	}

	else
	{
		Insert(here->children[input[index] - '0'], input, index + 1);
	}
}

void Delete_node(node* deleted_node)
{
	if (deleted_node == NULL)
		return;

	for (int i = 0; i < 10; i++)
		if (deleted_node->children[i] != NULL)
			Delete_node(deleted_node->children[i]);

	delete deleted_node;
}

bool Solve(node* here, string input, int index)
{
	if (index == input.size())
	{
		if (here->children_num > 0) //확인하는 input은 끝인데 children이 남아 있을때
			return false;

		else
			return true;
	}

	else if (here->finish == true) //확인하는 input은 남아있는데 끝인게 있을때
		return false;

	return Solve(here->children[input[index] - '0'], input, index + 1);
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> t;

	for (int tc = 0; tc < t; tc++)
	{
		node* root = Make_node();
		vector<string> input_list;

		cin >> n;

		for (int i = 0; i < n; i++)
		{
			string input;
			cin >> input;

			Insert(root, input, 0);
			input_list.push_back(input);
		}

		bool result = true;
		for (int i = 0; i < n; i++)
		{
			if (Solve(root, input_list[i], 0) == false)
			{
				result = false;
				break;
			}
		}

		if (result == true)
			cout << "YES" << "\n";
		else
			cout << "NO" << "\n";

		Delete_node(root);
	}


	return 0;
}