트라이(Trie) 자료구조

Base. 트리

=>트리는 노드(node)와 에지(edge)로 구성되는 계층관계를 나타내는 자료구조

 

1.트라이(trie)

=>트라이는 retrieval tree에서 나온 단어

=>문자열을 key로 사용하는 동적인 연관배열을 저장하는 트리의 확장된 자료구조

=>사용되는 곳은 Google의 dictionary, Excel의 Filtering 기능

 

https://brunch.co.kr/@springboot/75

트라이(Trie) 자료구조

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

5052번: 전화번호 목록

=>Trie로 문제를 짜보면 이해가 더 빠를 것이다

 

 

/*트라이:문자열을 저장하는 자료구조에서 가장 효율적인 문자열 검색 알고리즘
그것은 바로 "Trie"(트라이)
*/
#include<iostream>
using namespace std;

char Map[10001][12];//만개의 전화번호 목록에서 12자리수~

struct Trie
{
	bool Finish;//끝나는 지점 표시
	Trie* next[10]; //0부터 9까지 포인터 배열

	Trie() :Finish(false)
	{
		memset(next, false, sizeof(next));
	}
	~Trie()
	{
		for (int i = 0; i < 10; i++)
		{
			if (next[i])delete next[i];
		}
	}
	void insert(const char *key)
	{
		if (*key == '\0')
		{
			Finish = true;//문자열 끝나는 지점 표시
		}
		else
		{
			int cur = *key - '0';//시작문자열 자르기
			if (next[cur] == NULL)//현재노드의 숫자가 null이면
			{
				next[cur] = new Trie();
				//노드안에 동적할당을 통해 배열만들기
			}
			next[cur]->insert(key + 1);//현재노드에서 재귀를 통해 한글자씩연결
		}
	}
	int find(const char *key)
	{
		if (*key == '\0')return 0;
		if (Finish)return 2;

		int cur = *key - '0';
		
		return next[cur]->find(key + 1);
	}
};
char Map[10001][12];
int T, n;
int main()
{
	scanf("%d", &T);
	for (int i = 0; i < T; i++)
	{
		scanf("%d", &n);
		Trie *root = new Trie(); //처음 노드 생성 
		int flag = 0;

		for (int j = 0; j < n; j++)
		{
			scanf("%s", Map[j]);
			root->insert(Map[j]); //각 문자열 연결 !
		}
		for (int j = 0; j < n; j++)
		{
			if (root->find(Map[j]) == 2)
			{
				flag = 1;
			}
		}
		if (flag == 1)
			printf("NO\n");
		else printf("YES\n");

		delete root;
	}
}