트라이(Trie)Prefix Tree, Digital Search Tree, Retrieval Tree문자열을 빠르게 검색할 수 있는 자료구조K진 트리 구조 (문자열 K를 담을 수 있는 트리)단어 사전을 트라이로 생성 후 찾을 단어를 트라이를 사용하여 검색한다.트라이의 root 노드는 항상 공백문자열 상태이다. 구축하기트라이 노드 설계class Node { Node child[]; boolean isWord; }단어 사전의 입력할 단어를 트라이에 삽입루트 노드부터 시작하여 단어의 첫 글자부터 트라이를 탐색만약, 현재 노드의 자식 중 현재 입력 중인 철자에 해당하는 자식이 있다면, 현재 노드를 해당하는 자식 노드로 이동만약, 현재 노드의 자식 중 현재 입력 중인 철자에 해당하는 자식이 없다면, 새로운 자식..
https://www.acmicpc.net/problem/9202알고리즘 분류 : 자료 구조, 그래프 이론, 문자열, 브루트포스 알고리즘, 그래프 탐색, 트리, 깊이 우선 탐색, 백트래킹, 트라이❓문제🔅해석Trie 알고리즘을 활용하여 문제를 해결한다. 먼저, 입력받은 단어들로 Trie를 생성한다."ACM'을 입력받았다면 아래와 같이 Trie 객체가 생성된다. for문을 순회하여 Trie 객체인 root를 완성하면 뒤에 N개의 맵을 입력받아 탐색한다. dfs를 작성할 때는 아래 6단계를 거쳐 작성하는 것을 추천한다. 1. 체크인visited 배열에 true 를 입력하고 현재 map 좌표에 있는 알파벳 하나를 Stringbuilder에 붙인다. 2. 목적지인가목적지의 기준은 1) 현재 노드가 단어이면서, ..