[백준][C++] 14725: 개미굴

문제

14725번: 개미굴

풀이

문자열, 트라이

하늘색 박스가 하나의 Trie

 

이전 트라이 문제와 달리 접두사를 챙길 필요가 없다. 그러므로 Trie 구조체의 멤버 변수를 map<string, Trie*>로 두어 특정 string이 어떤 자식 노드를 가리키는지만 저장해 둔다. 

Trie에 string을 입력할 때는, map에 입력되는 string이 있는지 확인하고 없다면 새로운 Trie를 생성하여 map에 현재 string과 같이 저장한다.

출력 때는, 노드의 깊이도 같이 인자로 넣어주어 "--"가 현재 깊이만큼 출력된 다음, map에 있는 string이 출력되도록 한다. 

코드

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

using namespace std;

struct Trie
{
	map<string, Trie*> child;

	~Trie()
	{
		for (pair<string, Trie*> c : child)
		{
			delete c.second;
		}
	}

	void InsertWord(vector<string>& wordList, int idx)
	{
		if (wordList.size() == idx)
		{
			return;
		}

		// 현재 Trie의 child 중에서 wordList[idx]가 없다면 Trie를 새로 만들어서 child에 넣는다.
		if (child.find(wordList[idx]) == child.end())
		{
			Trie* trie = new Trie();

			child.insert(make_pair(wordList[idx], trie));
		}

		// wordList[idx]를 넣은 child로 가서 wordList[idx + 1]를 넣는다.
		child[wordList[idx]]->InsertWord(wordList, idx + 1);
	}

	void Print(int depth)
	{
		for (pair<string, Trie*> c : child)
		{
			for (int i = 0; i < depth; ++i)
			{
				cout << "--";
			}
			cout << c.first << '\n';

			c.second->Print(depth + 1);
		}
	}
};

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	Trie trie;

	while (N--)
	{
		int K;
		cin >> K;

		vector<string> wordList;
		string word;

		while (K--)
		{
			cin >> word;
			wordList.push_back(word);
		}

		trie.InsertWord(wordList, 0);
	}

	trie.Print(0);

	return 0;
}