문제

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

---

입력

첫 번째 줄은 먹이의 정보 개수 N

두 번째 줄부터 N+1 번째 줄까지 먹이 정보 개수 K (1 ≤ K ≤ 15)가 주어진다.

다음 K개의 입력은 로봇 개미가 왼쪽부터 순서대로 각 층마다 지나온 방에 있는 먹이 정보

---

출력

개미굴의 시각화된 구조

---

풀이

제한조건

• 1 ≤ N ≤ 1000
• 1 ≤ K ≤ 15
• 1 ≤ t ≤ 15

접근방법

Trie 구조 응용
Trie 구조를 조금 응용하면 쉽게 풀 수 있다.

Trie 구조에서 알파벳 1개 단위로 하위로 연결되었다면,
해당 문제에서는 단어 단위로 구분하여 아래로 쭉 연결하면 된다.

(Trie 구조를 모른다면? : https://velog.io/@hyeokkr/Trie)

전통적인 Trie구조에서 구현해야할 기능도 모두 구현할 필요가 없다.
단순히 삽입 기능과 출력기능만 추가하면 된다.

우선 Trie구조에서 사용할 TrieNode를 만들어 보자.

class TrieNode {
		private Map<String, TrieNode> childs = new TreeMap<>();

		public Map<String, TrieNode> getChilds() {
			return childs;
		}

전통적인 Trie 구조 처럼, 어디가 마지막인지, 표시할 필요도 없다.
단지 하위 구조를 잡기 위해 Map형태로 childs만 가지면 된다.
구현체를 TreeMap을 사용한 이유는 출력조건에 사전 순서가 앞서는 먹이 정보가 먼저 나오기 때문이다.

이제 Trie 구조를 잡아보자.

class Trie {
		private TrieNode root;
        
        public void insert(...){
        	...
        };
        public void print(...){
        	...
        };

문제를 풀기위해 삽입과 출력만 만든다.

public void insert(String[] words) {
	TrieNode node = root;
    for (int i = 1; i < words.length; ++i)
    	node = node.getChilds()
        .computeIfAbsent(words[i], w -> new TrieNode());
}

단순하다. 입력이 2 KIWI BANANA와 같은 형식이므로,
KIWI > BANANA 순으로 구조가 잡히므로 문자열배열을 통째로 넘겨서 1번째부터 처리하면 된다.

Map 구조의 childs에서 word[i]에 해당하는 키를 찾고,

• 있다면 해당 단어의 하위로 이동
• 없다면 새로운 키 생성
  와 같은 과정을 거친다.

출력의 경우에는 TreeMap을 통해 순서대로 접근이 가능하므로, DFS처럼 하나씩 출력하면 된다.

N의 크기가 크지 않아, 사실 다른 방식으로도 접근할 수 있을듯 하다.
다만, Trie 형태의 자료구조만 알고 있다면, 굉장히 쉽게 해결 할 수 있는문제로 Trie 구조의 개념을 이해해 보자.

---

코드

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

public class Main {
	static class Trie {
		private TrieNode root;

		Trie() {
			root = new TrieNode();
		}

		public void insert(String[] words) {
			TrieNode node = root;
			for (int i = 1; i < words.length; ++i)
				node = node.getChilds().computeIfAbsent(words[i], w -> new TrieNode());
		}

		public void print() {
			StringBuilder sb = new StringBuilder();
			for (String word : root.childs.keySet()) {
				sb.append(word).append("\n");
				if (!root.getChilds().get(word).getChilds().isEmpty()) {
					print(sb, root.getChilds().get(word).getChilds(), "--");
				}
			}

			System.out.println(sb);
		}

		private void print(StringBuilder sb, Map<String, TrieNode> childs, String s) {
			for (String word : childs.keySet()) {
				sb.append(s).append(word).append("\n");
				if (!childs.get(word).getChilds().isEmpty()) {
					print(sb, childs.get(word).getChilds(), s + "--");
				}
			}
		}
	}

	static class TrieNode {
		private Map<String, TrieNode> childs = new TreeMap<>();

		public Map<String, TrieNode> getChilds() {
			return childs;
		}
	}

	static int N;

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

		N = stoi(in.readLine());

		Trie trie = new Trie();
		for (int i = 0; i < N; ++i) {
			String[] inputs = in.readLine().split(" ");
			trie.insert(inputs);
		}
		trie.print();
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}