Trie

출처 백준 9202 Boggle 접근 Backtracking 특정 단어를 한 글자씩 찾아들어가면서 단어 사전에 존재하는지 확인하는 방식은 전형적인 DFS의 형태입니다. 주어진 단어의 개수가 w < 300,000 이지만 탐색해야 하는 전체 Boggle 보드의 크기가 4X4이고, 이러한 Boggle의 개수가 b < 30이기 때문에 DFS 자체는 많은 시간복잡도가 필요하지 않습니다. DFS 탐색 과정에서 다음 글자를 추가했을 때, 단어 사전에 포함된 단어를 만들 수 있는지를 빠르게 확인하여 불가능한 경우를 가지치기(pruning)한다면, 시간복잡도를 더욱 줄일 수 있습니다. 이러한 기법을 Backtracking이라고 합니다. ...