[백준 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의 이름을 저장합니다.

 

 

	import java.io.BufferedReader;
	import java.io.InputStreamReader;
	import java.util.ArrayList;
	import java.util.Collections;
	import java.util.Comparator;
	import java.util.StringTokenizer;
	public class p14725 {
	static StringBuilder sb;
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int n = Integer.parseInt(br.readLine());
	StringTokenizer stz;
	Trie trie = new Trie("");
	Trie node;
	sb = new StringBuilder();
	while(n --> 0) {
	stz = new StringTokenizer(br.readLine());
	int k = Integer.parseInt(stz.nextToken());
	node = trie;
	while(k --> 0) {
	String name = stz.nextToken();
	int index = -1;
	for(int i = 0; i < node.list.size(); i++) {
	if(node.list.get(i).name.equals(name)) {
	index = i;
	break;
	}
	}
	if(index == -1) {
	node.list.add(new Trie(name));
	node = node.list.get(node.list.size()-1);
	}
	else {
	node = node.list.get(index);
	}
	}
	}
	print(trie, -1);
	System.out.println(sb.toString());
	}
	public static void print(Trie trie, int depth) {
	Collections.sort(trie.list, new Comparator<Trie>() {
	@Override
	public int compare(Trie o1, Trie o2) {
	return o1.name.compareTo(o2.name);
	}
	});
	if(depth != -1) {
	for(int i = 0; i < depth; i++) {
	sb.append("--");
	}
	sb.append(trie.name).append("\n");
	}
	for(Trie tr : trie.list) {
	print(tr, depth+1);
	}
	}
	static class Trie{
	ArrayList<Trie> list;
	String name;
	Trie(String name) {
	list = new ArrayList<>();
	this.name = name;
	}
	}
	}

view raw p14725.java hosted with ❤ by GitHub