백준
백준 14725 개미굴
콩순이냉장고
2021. 11. 12. 18:20
문제 URL : https://www.acmicpc.net/problem/14725
14725번: 개미굴
첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이
www.acmicpc.net
문제 접근법 :
map을 이용해서 trie구조를 만들어 트리를 구성하는 문제입니다.
트리구조만 제대로 형성된다면 dfs로 search하는 과정을 보이라는 문제입니다.
소스코드 :
|
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
|
#include <bits/stdc++.h>
using namespace std;
int n;
struct trie {
map<string, trie*> tr;
void insert(vector<string> v,int idx=0) {
if (v.size() <= idx)return;
if (tr.count(v[idx]) == 0)
tr[v[idx]] = new trie();
tr[v[idx]]->insert(v, idx + 1);
}
};
trie* root;
void dfs(trie* cur,string t, string s = "") {
cout<<s<< t << "\n";
for (auto it : cur->tr)
dfs(it.second, it.first, s + "--");
}
void input(){
cin >> n;
root = new trie();
for (int i = 0; i < n; i++) {
int a;
cin >> a;
vector<string> v(a);
for (int j = 0; j < a; j++)
cin >> v[j];
root->insert(v);
}
}
void solve() {
for (auto it : root->tr) {
dfs(it.second, it.first);
}
}
int main(){
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.
공감도 눌러주실꺼죠?