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

문제 읽기🤔

---

 

문제

개미는(뚠뚠) 오늘도(뚠뚠) 열심히(뚠뚠)  일을 하네.

개미는 아무말도 하지 않지만 땀을 뻘뻘 흘리면서 매일 매일을 살길 위해서 열심히 일을 하네.

한 치 앞도(뚠뚠) 모르는(뚠뚠) 험한 이 세상(뚠뚠) 그렇지만(뚠뚠) 오늘도 행복한 개미들!

우리의 천재 공학자 윤수는 이 개미들이 왜 행복한지 궁금해졌다.

행복의 비결이 개미가 사는 개미굴에 있다고 생각한 윤수는 개미굴의 구조를 알아보기 위해 로봇 개미를 만들었다.

로봇 개미는 센서가 있어 개미굴의 각 층에 먹이가 있는 방을 따라 내려가다 더 이상 내려갈 수 없으면 그 자리에서 움직이지 않고 신호를 보낸다.

이 신호로 로봇 개미는 개미굴 각 층을 따라 내려오면서 알게 된 각 방에 저장된 먹이 정보를 윤수한테 알려줄 수 있다.

로봇 개미 개발을 완료한 윤수는 개미굴 탐사를 앞두고 로봇 개미를 테스트 해보기 위해 위 그림의 개미굴에 로봇 개미를 투입했다. (로봇 개미의 수는 각 개미굴의 저장소를 모두 확인할 수 있을 만큼 넣는다.)

다음은 로봇 개미들이 윤수에게 보내준 정보다.

• KIWI BANANA
• KIWI APPLE
• APPLE APPLE
• APPLE BANANA KIWI

(공백을 기준으로 왼쪽부터 순서대로 로봇 개미가 각 층마다 지나온 방에 있는 먹이 이름을 뜻한다.)

윤수는 로봇 개미들이 보내준 정보를 바탕으로 다음과 같이 개미굴의 구조를 손으로 그려봤다.

APPLE
--APPLE
--BANANA
----KIWI
KIWI
--APPLE
--BANANA

(개미굴의 각 층은 "--" 로 구분을 하였다.

또 같은 층에 여러 개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.)

우리의 천재 공학자 윤수는 복잡한 개미굴들을 일일이 손으로 그리기 힘들어 우리에게 그려달라고 부탁했다.

한치 앞도 모르는 험한 이세상 그렇지만 오늘도 행복한 개미들!

행복의 비결을 알기 위해 윤수를 도와 개미굴이 어떤 구조인지 확인해보자.

입력

첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다.  (1 ≤ N ≤ 1000)

두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정보 개수 K가 주어진다. (1 ≤ K ≤ 15)

다음 K개의 입력은 로봇 개미가 왼쪽부터 순서대로 각 층마다 지나온 방에 있는 먹이 정보이며 먹이 이름 길이 t는 (1 ≤ t ≤ 15) 이다. 

출력

개미굴의 시각화된 구조를 출력하여라.

개미굴의 각 층을 "--" 로 구분하며, 같은 층에 여러개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.

 

예제 입력 1

3
2 B A
4 A B C D
2 A C

예제 출력 1

A
--B
----C
------D
--C
B
--A

 

 

문제 풀이📝

---

처음에는 트리의 각 노드에 단어를 멤버변수로 저장하려고 했다.

그러나 사전순으로 출력해야 한다는 문제의 조건을 따르기 위해서는, 단어를 하나 추가할 때 마다 트리의 같은 층에 있는 노드들과 일일이 비교하여 올바른 위치를 찾아주어야 했다.

Java의 compareTo() 메소드는 두 문자열의 문자를 하나하나씩 대조하며 비교하기 때문에 O(N)의 시간복잡도를 가진다.

그러므로 최악의 경우 층마다 모든 자식들을 순회하면서 문자열을 비교해야 하기 때문에 시간초과가 날 것이라고 예측했다.

 

문자열 저장과 탐색을 좀 더 효율적으로 할 수는 없을까? 고민하는 도중, 이전에 스터디에서 배웠던 트라이(Trie) 알고리즘이 떠올랐다.

트라이 알고리즘은 문자열의 저장, 탐색 최적화되어 있는 알고리즘이다.

메모리를 많이 사용하게 된다는 단점이 있지만, 문제의 입력 조건에 따른다면 최악의 경우에도 프로그램이 터지지 않을 것이라 확신했다.

 

트라이 알고리즘

 

노드의 자식 노드들을 TreeMap에 저장하여 사전순으로 저장됨을 보장하였고, 단어가 완성됐음을 의미하는 isWord 플래그를 두어 단어의 끝임을 나타냈다.

또한, 노드에 현재 단어와 현재 단어가 속한 층 수를 기록하여 출력 시 사용하였다.

예를 들어

A JAM

이라는 입력이 들어왔다면

트라이 알고리즘 응용

 

위와 같이 트리에 단어들을 저장한 후, 출력시에는 root 노드부터 DFS 방식으로 자식 노드들을 순회하였다.

isWord 플래그를 만나면 해당 노드에 저장되어 있는 단어(word)를 출력하도록 했고

더 탐색할 자식 노드가 있다면 depth의 크기만큼 "--"를 반복해서 출력해주었다.

 

 

구현🛠️

---

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


// 개미굴~
public class Main_14725 {

    static class Trie {

        static class TrieNode {

            String word;    // 해당 노드에 저장되어 있는 단어
            int depth;  // 해당 단어가 개미굴의 몇 층에 있는지
            TreeMap<Character, TrieNode> children;
            boolean isWord;

            public TrieNode(String word, int depth){
                this.word = word;
                this.depth = depth;
                this.children = new TreeMap<>();
                this.isWord = false;
            }
        }

        TrieNode root;
        int depth;

        public Trie(){
            this.root = new TrieNode("", 0);
        }

        // Trie 트리에 삽입
        public void insert(String[] words){
            TrieNode node = this.root;
            depth = 0;
            for (String word : words){
                StringBuilder subWord = new StringBuilder();
                for (Character c : word.toCharArray()){

                    subWord.append(c);
                    // computeIfAbsent(): Map에 key에 대응하는 value가 존재할 때: 해당 value 반환, 존재하지 않을 때: 해당 함수 실행
                    // 자식 노드 존재 -> 자식노드로 이동, 자식 노드 없다면 새로 Node 만들어서 넣어줌
                    node = node.children.computeIfAbsent(c, child -> new TrieNode(subWord.toString(), depth));
                }
                node.isWord = true; // 해당 단어의 마지막 문자에는 true 체크
                depth++;
            }
        }

        // Trie 트리를 순회하면서 출력 문자열을 만듦
        public void print(TrieNode root){
            TrieNode node = root;
            for (Character c : node.children.keySet()){

                // 해당 단어의 마지막 문자인 경우 -> 단어 완성!
                if (node.children.get(c).isWord){
                    // 이후에 연결된 문자가 있다면 -> 다음 depth의 단어가 있다는 뜻, 다음 층으로 내려간다.
                    if (node.children.get(c).depth != 0){
                        result.append("--".repeat(node.children.get(c).depth)); // "--"을 depth 만큼 곱한다, Java11부터 사용 가능
                    }
                    result.append(node.children.get(c).word);
                    result.append("\n");
                }
                print(node.children.get(c));
            }
        }
    }

    static int N;
    static Trie trie;
    static StringBuilder result = new StringBuilder();

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

        N = Integer.parseInt(br.readLine());
        trie = new Trie();

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int K = Integer.parseInt(st.nextToken());
            String[] inputs = new String[K];
            for (int j = 0; j < K; j++) {
                inputs[j] = st.nextToken();
            }
            trie.insert(inputs);    // 단어 입력
        }

        trie.print(trie.root);  // 입력받은 단어들을 바탕으로한 개미굴 출력
        System.out.println(result);
    }
}

 

 

실행결과✅

---