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
'알고리즘 > 트리' 카테고리의 다른 글
[백준][JAVA] 1240번 노드사이의 거리 (0) | 2024.01.18 |
---|---|
[백준][JAVA] 9934번 완전 이진 트리 (0) | 2024.01.17 |
[백준][JAVA] 11438번 LCA 2 (1) | 2023.12.29 |
[백준][JAVA] 11437번 LCA (1) | 2023.12.28 |
[백준][JAVA] 15681번 트리와 쿼리 (0) | 2023.12.24 |