본문 바로가기
알고리즘/트리

[백준][JAVA] 14725번 개미굴

by 박뀨뀨 2024. 3. 11.
 

14725번: 개미굴

첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개가 주어진다. 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정

www.acmicpc.net

코드

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

public class Main {

    // 트라이 노드
    static class Node {
        TreeMap<String, Node> children;

        public Node() {
            children = new TreeMap<>();
        }
    }

    // 트라이
    static class Trie {
        Node root;

        public Trie() {
            this.root = new Node();
        }
    }

    static StringBuilder sb = new StringBuilder();

    // 트라이 생성
    static Trie trie = new Trie();


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 먹이의 정보 개수 (1 <= N <= 1000)
        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            // 로봇 개미 한마리가 보내준 먹이 정보 개수 (1 <= K <= 15)
            int K = Integer.parseInt(st.nextToken());

            // 가리키고 있는 노드. 트라이의 루트 노드
            Node cur = trie.root;

            for (int j = 0; j < K; j++) {
                String word = st.nextToken();
                // 해당 단어 없으면 노드 새로 생성
                cur.children.computeIfAbsent(word, k -> new Node());
                // 가리킬 노드 이동
                cur = cur.children.get(word);
            }
        }

        // 개미굴의 시각화된 구조 출력
        print(0, trie.root);
        System.out.print(sb);
    }

    static void print(int depth, Node cur) {

        for (String word : cur.children.keySet()) {
            for (int i = 0; i < depth; i++) {
                sb.append("--");
            }
            sb.append(word).append("\n");
            print(depth + 1, cur.children.get(word));
        }
    }
}
728x90