트라이 (Trie)
출처: https://www.crocus.co.kr/1053 [Crocus]
트라이(Trie) 자료구조
목차 1. 트라이(Trie)란? 2. 트라이(Trie) 이해하기 3. 트라이(Trie)의 단점 4. 트라이(Trie) 접목하기 5. 트라이(Trie) 문제 풀어보기 트라이(Trie)란? 문자열에 특화된 자료 구조인 트라이(Trie)는 문자열 집합..
www.crocus.co.kr
트라이 (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
문제 상근이는 보드 게임 "Boggle"을 엄청나게 좋아한다. Boggle은 글자가 쓰여 있는 주사위로 이루어진 4×4 크기의 그리드에서 최대한 많은 단어를 찾는 게임이다. 상근이는 한 번도 부인을 Boggle로 이겨본 적이 없다. 이렇게 질 때마다 상근이는 쓰레기 버리기, 설거지와 같은 일을 해야 한다. 이제 상근이는 프로그램을 작성해서 부인을 이겨보려고 한다. Boggle에서 단어는 인접한 글자(가로, 세로, 대각선)를 이용해서 만들 수 있다. 하지
www.acmicpc.net
이 문제의 핵심은 트라이에 dfs 완전탐색을 적용해야 한다는 것이다. 탐색을 하는 도중 중복 방문을 하거나 범위를 벗어나거나 지정된 문자열의 크기를 넘어가면 return시키고 추가로 다음에 방문한 문자가 트라이에 저장이 돼 있지 않은 경우 단어를 만들 수 없으므로 이때도 방문을 다시 false로 고치고 return을 해야한다. 그리고 진행을 하다가 단어 마침표 지점인 finish가 있으면 그때의 단어를 추가한다. 이 문제에서는 단어를 사전순으로 저장해야하고 중복 삽입이 없어야 돼서 set을 이용하여 데이터를 관리하면 좀 더 쉽게 구현을 할 수가 있다.
그래서 정리하자면 트라이 + set + dfs를 활용하는 매우 매우 어려웠던 문제..
소스코드