https://www.acmicpc.net/problem/14725
각 층의 방에 연결된 아래 층의 방들을 저장하도록 하는 트리 형태로 구성한다.
HashMap<String , node>의 형태로 반복하여 Root가 되는 방부터 하위 구조가 만들어지도록 한다.
문제에서 그림으로 설명하는 개미굴을 표현해보면
1층
Root : HashMap<String , node> : “APPLE”, “KIWI”
2층
“APPLE” : HashMap<String, node> : “APPLE”, BANANA”
“KIWI” : HashMap<String, node> : “APPLE”, “BANANA”
3층
“APPLE” : HashMap<String, node> : Empty
“BNANA” : HashMap<String, node> : “KIWI”
“APPLE” : HashMap<String, node> : Empty
“KIWI” : HashMap<String, node> : Empty
4층
“KIWI” : HashMap<String, node> : Empty
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class Main {
static Node root = new Node();
static class Node{
HashMap<String, Node> child;
public Node(){
child = new HashMap<>();
}
}
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
for(int i=0;i<N;i++){
st = new StringTokenizer(br.readLine()," ");
int K = Integer.parseInt(st.nextToken());
Node cur = root;
for(int j=0;j<K;j++){
String temp = st.nextToken();
if(!cur.child.containsKey(temp)){
cur.child.put(temp, new Node());
}
cur = cur.child.get(temp);
}
}
print(root, "");
System.out.print(sb);
}
static void print(Node cur, String s){
//현재 방에 자식 구조 가져오기
ArrayList<String> list = new ArrayList<>(cur.child.keySet());
Collections.sort(list); //사전 순 정렬
//정렬 이후 사전 순으로 표시 후 탐색
for(String str : list){
sb.append(s).append(str).append("\n");
print(cur.child.get(str), s +"--");
}
}
}