백준14725 개미굴

작성일 | In

문제 링크

  • http://icpc.me/14725

사용 알고리즘

  • Trie

풀이

원래 트라이의 각 노드에는 글자 하나가 저장이 되어있고 child배열에는 다음에 나올 글자가 저장되어 있습니다.
이 문제에서는 트라이랑 비슷한 자료구조를 만들어서, 각 노드ㅕㅊ에는 단어를 저장하고 child배열에는 다음에 나올 단어를 저장하면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

struct Node{
	map<string, Node> child;
}root;

void insert(Node &v, vector<string> &arr, int idx){
	if(idx == arr.size()) return;

	if(!v.child.count(arr[idx])) v.child[arr[idx]] = Node();
	insert(v.child[arr[idx]], arr, idx+1);
}

void dfs(Node &v, int dep = 0){
	for(auto i : v.child){
		for(int j=0; j<dep; j++) cout << "--";
		cout << i.first << "\n";
		dfs(i.second, dep+1);
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while(t--){
		int n; cin >> n;
		vector<string> v(n);
		for(int i=0; i<n; i++) cin >> v[i];
		insert(root, v, 0);
	}
	dfs(root);
}