백준 14725번 : 개미굴 - Trie , Java

 

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

14725번: 개미굴

 

트라이의 성질을 이용하여 트리구조를 구현해야한다.

이때 출력은 사전순으로 해야하기 때문에

자바로 문제를 푸는 경우엔 TreeMap을 활용하면 key값을 기준으로 알아서 정렬이 된다.

 

출력은 정렬된 TreeMap을 활용해 하위 노드들을 중위순회로 돌면 된다.

 

 

//package org.example;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    class Trie {
        TreeMap<String, Trie> child = new TreeMap<>();
    }
    //출력용
    private StringBuilder sb = new StringBuilder();
    public void print(Trie root, int depth) {
        Set keys = root.child.keySet();

        for (Object key : keys) {
            for (int i = 0; i < depth; i++) {
                sb.append("--");
            }
            sb.append(key).append("\n");
            print(root.child.get(key), depth + 1);
        }
    }

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Trie root = new Trie();

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

            int K = Integer.parseInt(st.nextToken());

            Trie cur = root;
            //Trie 생성
            for (int j = 0; j < K; j++) {
                String str = st.nextToken();
                if (!cur.child.containsKey(str)) {
                    cur.child.put(str, new Trie());
                }
                cur = cur.child.get(str);
            }
        }
        print(root, 0);
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}