[삼성SDS] 24년 하반기 대학생 알고리즘 특강(Day4) : 자료구조(Trie 트라이)

트라이(Trie)

• Prefix Tree, Digital Search Tree, Retrieval Tree
• 문자열을 빠르게 검색할 수 있는 자료구조
• K진 트리 구조 (문자열 K를 담을 수 있는 트리)
• 단어 사전을 트라이로 생성 후 찾을 단어를 트라이를 사용하여 검색한다.
• 트라이의 root 노드는 항상 공백문자열 상태이다.

 

구축하기

1. 트라이 노드 설계
2. class Node { Node child[]; boolean isWord; }
3. 단어 사전의 입력할 단어를 트라이에 삽입
4. 루트 노드부터 시작하여 단어의 첫 글자부터 트라이를 탐색
5. 만약, 현재 노드의 자식 중 현재 입력 중인 철자에 해당하는 자식이 있다면, 현재 노드를 해당하는 자식 노드로 이동
6. 만약, 현재 노드의 자식 중 현재 입력 중인 철자에 해당하는 자식이 없다면, 새로운 자식을 추가
7. 단어를 삽입 후, 탐색된 마지막 노드에 현재 입력된 단어의 정보를 추가

private static void insert(String word) {
    TrieNode current = root;
    for (int i = 0; i < word.length(); i++) {
        int wordIndex = word.charAt(i) - 'A';
        if (current.children[wordIndex] == null) {	//4. 해당하는 자식이 없다면
            current.children[wordIndex] = new TrieNode();	// 새로운 자식 추가
        }
        current = current.children[wordIndex];
    }
    current.isWord = true;
}

 

 

검색하기

1. 루트 노드부터 시작하여 검색할 단어의 첫 글자부터 트라이를 검색
2. 만약, 현재 노드의 자식 노드 중 현재 입력 중인 철자에 해당하는 자식이 있다면, 현재 노드를 해당하는 자식 노드로 이동
3. 만약, 현재 노드의 자식 노드 중 현재 입력 중인 철자에 해당하는 자식이 없다면, 검색할 단어는 단어사전에 존재하지 않는 단어로 처리
4. 탐색이 완료되었다면, 탐색된 마지막 노드의 정보를 이용

//2. 현재 노드의 자식 노드 중 현재 입력 중인 철자에 해당하는 자식이 있다면
if (node.children[map[nextY][nextX] - 'A'] != null)

 

 

예제 문제

백준 9202번 : Boggle

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

 

 

[코테] 백준 9202번 : Boggle (java)