[JAVA] BOJ 백준 14725 개미굴

문제 바로 가기 > 문제 링크

💡
1. 기존 Trie 알고리즘과 달리 층별로 삽입되는 String들을 하나의 변수에 넣어서 넘기지 않음. 그러므로 삽입 시, parent를 넘겨주어야 함.
2. 출력 시, map을 list로 변환하여 정렬해준다. 또한 백트래킹처럼 연결된 모든 것을 출력한 뒤 다음 child를 출력해야 하므로 재귀를 사용한다.

import java.util.*;
import java.io.*;

public class boj_14725 {
	static class Node{
		Map<String, Node> childNode = new HashMap<>();
		boolean end;
	}
	static class MakeAntHole{
		Node rootNode = new Node();
		Node insert(Node root, String in, boolean end) {
			Node r = root.childNode.computeIfAbsent(in, key -> new Node());
			r.end = end;
			return r;
		}
		void print(Node node, int depth) {
			List<String> antList = new ArrayList<>(node.childNode.keySet());
			antList.sort((o1, o2) -> o1.compareTo(o2));
			for(String hole : antList) {
				printDepth(depth);
				System.out.println(hole);
				if(!node.childNode.getOrDefault(hole, null).end) {
					print(node.childNode.get(hole), depth+1);
				}
			}
		}
		void printDepth(int cnt) {
			for(int i=0; i<cnt; i++) {
				System.out.print("--");
			}
		}
	}
	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(bf.readLine());
		MakeAntHole hole = new MakeAntHole();
		Node root = hole.rootNode;
		for(int i=0; i<T; i++) {
			StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
			int N = Integer.parseInt(st.nextToken());
			Node node = root;
			for(int j=0; j<N; j++) {
				node = hole.insert(node, st.nextToken(), j==N-1 ? true : false);
			}
		}
		hole.print(root, 0);
	}
	
}

출처

Map 정렬하기