https://www.acmicpc.net/problem/14725
14725번: 개미굴
첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이
www.acmicpc.net
개미굴의 각 저장소들을 트라이 방식으로 저장할 수 있습니다.
A B C 이런식으로 입력이 들어오면 A 다음 B 다음 C 이런식으로 저장하는 방식입니다.
다만 들어오는 데이터가 문자열 방식이므로 일반적인 배열로는 할 수 없으며 map를 사용합니다.
m.find(str) 메소드를 이용하여 해당 depth에 문자열이 저장되었는지 확인 후
저장되었다면 다음 depth로 이동, 저장되지 않았다면 해당 depth의 map에 문자열을 저장 후 다음 depth로 이동합니다.
출력은 개미굴의 구조를 사전 순으로 출력합니다.
map은 이미 정렬이 된 자료구조이므로 iterator를 이용하여 사전 순으로 출력해줍니다.
|
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
#include <iostream>
#include <map>
#include <string>
#define MAX 16
using namespace std;
string list[MAX];
int N, M;
typedef struct Trie {
map<string, Trie*> m;
~Trie() {
map<string, Trie*>::iterator iter = m.begin();
for (; iter != m.end(); iter++) {
delete (*iter).second;
}
}
void insert(int idx) {
if (idx == M) return;
if (m.find(list[idx]) == m.end()) {
m.insert({ list[idx], new Trie() });
m[list[idx]]->insert(idx + 1);
}
else {
m[list[idx]]->insert(idx + 1);
}
}
void find(int depth) {
map<string, Trie*>::iterator iter = m.begin();
for (; iter != m.end(); iter++) {
for (int i = 0; i < depth; i++) {
cout << "--";
}
cout << (*iter).first << '\n';
(*iter).second->find(depth + 1);
}
}
}Trie;
Trie *t;
void func() {
t->find(0);
}
void init() {
t = new Trie();
}
void input() {
init();
cin >> N;
for (int i = 0; i < N; i++) {
cin >> M;
for (int j = 0; j < M; j++) {
cin >> list[j];
}
t->insert(0);
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > Trie' 카테고리의 다른 글
| boj 5052 전화번호 목록 (0) | 2022.03.27 |
|---|
