[c++] 백준 14725 개미굴

백준 단계별로 풀어보기 [문자열 알고리즘 1] 개미굴

https://www.acmicpc.net/problem/14725

14725번: 개미굴

 

[풀이]

트라이 알고리즘 응용 문제이다. 먼저 문자열을 vector를 이용해 저장하고 map<string, *Node>를 이용해 트라이 구조를 나타낸다. 같은 층에 이미 똑같은 문자열이 존재한다면(경로가 존재), 그 다음 노드로 이동해서 단어를 삽입한다. 만약 존재하지 않는다면 새로 노드를 할당받아 단어를 저장한다. map은 key를 기준으로 오름차순 자동 정렬을 해주기 때문에 iterator로 map을 순회하면서 낮은 층부터 방문하면 된다.  

 

[코드]

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <string>

using namespace std;

struct Node {
	map<string, Node*> child;
	map<string, Node*>::iterator iter;
    
    	Node() {}
	~Node() {
		for (iter = child.begin(); iter != child.end(); iter++) {
			delete (*iter).second;
		}
	}

	void insert(vector<string> v, int idx) {
		if (idx == v.size()) return;
		string s = v[idx];
		iter = child.find(s);
		if (iter != child.end()) //이미 존재하는 경우
			iter->second->insert(v, idx + 1);
		else {
			Node* p = new Node();
			child.insert({ s, p });
			p->insert(v, idx + 1);
		}
	}

	void print(int level) {
		for (auto iter = child.begin(); iter != child.end(); iter++) {
			for (int i = 0; i < level; i++)
				cout << "--";
			cout << iter->first << "\n";
			iter->second->print(level + 1);
		}
	}
};

int main() {
	//trie 알고리즘
	Node* root = new Node();
	int n, k;
	string s;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> k;
		vector<string> v;
		for (int j = 0; j < k; j++) {
			cin >> s;
			v.push_back(s);
		}
		root->insert(v, 0);
	}

	root->print(0);
    
    delete root;
	return 0;
}