트라이 (Trie)

출처: https://www.crocus.co.kr/1053 [Crocus]

트라이(Trie) 자료구조

트라이 (Trie)란?

문자열에 특화된 자료 구조인 트라이(Trie)는 문자열 집합을 표현하는 트리 자료구조이며,

 

우리가 원하는 원소를 찾는 작업을 O(n)에 (단어길이 만에) 해결 할 수 있는 자료구조이다.

알파벳을 저장하려면 Trie 구조체 안에 Trie* next[26] 과 같이 포인터배열로 정의 할 수 있다. 

그리고 finish 변수를 만들어 단어를 저장시 그 지점에서 단어가 하나 끝나 있다는 표시를 할 수 있게 해 줘야 한다.

 

생성자

생성자로는 처음에 insert가 돼 있지 않은 상태이므로 for문을 25까지 돌며 next[i]=NULL값으로, finish=false로 초기화를 시켜줘야 한다.

 

소멸자

소멸자도 마찬가지로 25까지 반복문을 돌면서 next[i]가 존재한다면 delete를 시키면 된다.

 

insert

문자열(char * 형) 의 *key (value)가 '\0' 즉 문자열의 끝을 가리키고 있으면 이때finisi로 종료 표시를 해줘야 한다.

만약 아니라면 현재 *key (문자)가 있다는 뜻이므로 -'A'를 빼줘 정수형으로 변환 후에 현재 문자가 비어있다면 꼭 생성자로 현재 Trie를 생성하여 next 값에 넣어줘야한다.  그러고 나서  key+1로 다음값의 key로 넘긴다.

 

관련 문제

백준:https://www.acmicpc.net/problem/9202

9202번: Boggle

이 문제의 핵심은 트라이에 dfs 완전탐색을 적용해야 한다는 것이다. 탐색을 하는 도중 중복 방문을 하거나 범위를 벗어나거나 지정된 문자열의 크기를 넘어가면 return시키고 추가로 다음에 방문한 문자가 트라이에 저장이 돼 있지 않은 경우 단어를 만들 수 없으므로 이때도 방문을 다시 false로 고치고 return을 해야한다. 그리고 진행을 하다가 단어 마침표 지점인 finish가 있으면 그때의 단어를 추가한다. 이 문제에서는 단어를 사전순으로 저장해야하고 중복 삽입이 없어야 돼서 set을 이용하여 데이터를 관리하면 좀 더  쉽게 구현을 할 수가 있다. 

그래서 정리하자면 트라이 + set + dfs를 활용하는 매우 매우 어려웠던 문제..

소스코드