BOJ. Ant tunnel (14725)

[Link] https://www.acmicpc.net/problem/14725

Each input line is a path from the root of the ant tunnel. Inserting each token into a trie merges any prefix already present: a node’s children are the next foods that can follow that prefix. A TreeMap stores those children in lexicographic order, so a depth-first traversal visits siblings in the required order without sorting or copying them first.

During traversal, append -- once for every edge from the root, followed by the current token and a newline. Thus the root’s children have no prefix dashes, and each deeper level gains exactly one --.

If the total number of tokens is S and the trie contains V nodes, insertion takes O(S log V) time in the worst case with ordered maps, and traversal takes O(V) time. The trie uses O(V) space.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Map;
import java.util.TreeMap;

public class Main {
    private static final StringBuilder output = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(input.readLine());
        Trie root = new Trie();

        for (int i = 0; i < n; i++) {
            String[] foods = input.readLine().split(" ");
            Trie node = root;
            for (int j = 1; j < foods.length; j++) {
                node = node.children.computeIfAbsent(foods[j], key -> new Trie());
            }
        }

        root.print(0);
        System.out.print(output);
    }

    private static class Trie {
        private final TreeMap<String, Trie> children = new TreeMap<>();

        private void print(int depth) {
            for (Map.Entry<String, Trie> child : children.entrySet()) {
                for (int i = 0; i < depth; i++) {
                    output.append("--");
                }
                output.append(child.getKey()).append('\n');
                child.getValue().print(depth + 1);
            }
        }
    }
}