[백준 14725] 개미굴 (자바)

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

14725번: 개미굴

 

난이도 : 골드 2

 

트라이를 이용하여 풀었습니다. 트라이는 문제에서 주어진 그림처럼 문자열 트리라고 생각할 수 있습니다.

---

전역 변수

StringBuilder sb = 트라이 구조를 그려서 저장할 변수

함수

void main

입력을 받고 트라이를 구현합니다. 19번째 줄에서는 n개의 입력을 받고 24번째 줄에서는 한 줄의 입력에서 k개의 입력을 트라이에 넣습니다.

노드는 트라이를 탐색할 때 이용하는 변수인데 28번째 줄에서 노드의 리스트에 삽입해야 할 String이 있는지 검사합니다. 없다면 -1, 있다면 그 변수가 위치한 list의 index를 가집니다.

index가 -1이라면 현재 노드의 list에 String 변수를 추가합니다. 그리고 노드는 추가한 변수의 위치로 이동합니다.(자식)

index가 -1이 아니라면 해당 변수의 위치로 노드를 이동시킵니다.(자식)

(print 호출)

 

void print

재귀 형식으로 현재 노드의 list를 이름 순으로 정렬하고 현재 노드의 name을 StringBuilder에 추가합니다. 그 후 list의 값에 차례대로 접근하여 dfs합니다.

 

class Trie

list는 현재 Trie에서 밑에 자식을 저장합니다. name은 현재 Trie의 이름을 저장합니다.