[PS] 개미굴 / C++ (백준 14725번)

 

자료구조 Trie를 변형해서 풀 수 있는 문제

1. map< string, Trie* >로 next에 key값으로 string, value에 Trie의 포인터 값을 저장하게끔 map을 만들어 준 후, input 데이터를 저장해준다.
2. dfs형식의 print 함수를 적절히 만들어 next에 저장된 tree 형식의 데이터를 출력

 

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
using namespace std;

struct Trie {
	bool finish;
	map< string, Trie* > next;

	Trie() :finish(false) {};

	~Trie() {
		for (auto it = next.begin(); it != next.end(); it++)
			delete(it->second);
	};

	void insert(vector<string> vec, int cur, int last) {
		string key = vec[cur];
		if (next.find(key) == next.end()) {
			next.insert({ key, new Trie() });
		}
		if (cur == last - 1) {
			finish = true;
			return;
		}
		next[key]->insert(vec, cur + 1, last);
		return;
	}

	void print(int cur) {
		for (auto it = next.begin(); it != next.end(); it++) {
			for(int i=0; i<cur; i++)printf("--");
			cout << (*it).first << endl;
			((*it).second)->print(cur + 1);
		}
	}

};

int main()
{
	int n;
	Trie* tree = new Trie();
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int k;
		scanf("%d", &k);
		vector<string> vec;
		for (int j = 0; j < k; j++) {
			string str;
			cin >> str;
			vec.push_back(str);
		}
		tree->insert(vec, 0, k);
	}
	tree->print(0);
	return 0;
}