[Baekjoon,14725] 개미굴

무식한 방법

한 글자 단위로 접근

구조를 보면 트라이가 떠오른다. 문자들을 트라이에 모두 집어 넣는데 단어 사이에 각 계층이 연결된 것을 생각하며 넣어야 한다. 그 후 알파벳 순서로 $DFS$ 하듯이 탐색하며 단어들을 출력하고 현재 노드가 $terminal$인 경우 줄 바꿈을 해준다. 이때 중요한 것은 깊이에 따른 문자열 -- 출력인데 이는 자식 노드가 존재하고 현재 노드가 터미널인 경우 깊이만큼 --를 출력하면 된다.

구현

이에 대한 구현을 아래에서 볼 수 있다. 트라이 구조체를 활용하여 작성했다.

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

const int ALPAHBETS = 26;
int toNumber(char ch) { return ch - 'A'; }

struct TrieNode
{
	TrieNode* children[ALPAHBETS];
	// 이 노드가 종료 노드인가?
	bool terminal;
	TrieNode() : terminal(false)
	{
		memset(children, 0, sizeof(children));
	}
	~TrieNode()
	{
		for (int i = 0;i < ALPAHBETS;++i)
			if (children[i])
				delete children[i];
	}
	// 이 노드를 루트로 하는 트라이에 문자열 key를 추가한다.
	void insert(const char* key)
	{
		if (*key == 0)
			terminal = true;
		else
		{
			int next = toNumber(*key);
			if (children[next] == NULL)
				children[next] = new TrieNode();
			children[next]->insert(key + 1);
		}
	}
	// 이 노드를 루트로 하는 트라이에 문자열 key와 대응되는 노드를 찾는다.
	// 없다면 NULL을 반환한다.
	TrieNode* find(const char* key)
	{
		if (*key == 0)
			return this;
		int next = toNumber(*key);
		if (children[next] == NULL)
			return NULL;
		return children[next]->find(key + 1);
	}
};

int N;

void printRet(TrieNode* root, int depth)
{
	// 단어가 완성된 경우
	if (root->terminal)
		cout << endl;
	// 알파벳 순으로 탐색한다. 
	for (int i = 0;i < ALPAHBETS;++i)
		if (root->children[i] != NULL)
		{
			// 현재 노드가 터미널이면 다음 깊이를 증가시킨다. 
			int nextDepth = depth;
			if (root->terminal)
			{
				++nextDepth;
				for (int i = 0;i < depth;++i)
					cout << "--";
			}
			// 다음 노드의 글자 출력 
			cout << (char)(i + 'A');
			printRet(root->children[i], nextDepth);
		}
}

int main()
{
	cin >> N;

	TrieNode* trie = new TrieNode();
	for (int i = 0;i < N;++i)
	{
		int k;
		cin >> k;
		// 문자들을 연결시키기 위한 임시 노드
		TrieNode* tmp = trie;
		for (int j = 0;j < k;++j)
		{
			string s;
			cin >> s;
			tmp->insert(s.c_str());
			// 생성한 단어의 마지막 글자를 가르킨다. 
			tmp = tmp->find(s.c_str());
		}
	}

	printRet(trie,1);
	return 0;
}

더 나은 방법

문자열 단위로 접근

위보다 더 나은 방법이 있다. 이는 바로 문자 단위로 자식을 가리키지 않고 $map$을 이용하여 문자열 단위로 자식을 가리키는 것이다. 이 방법은 JusticeHui가 PS하는 블로그에서 알게 되었다.

구현

각 문자열 묶음을 트라이에 넣는 방식을 눈여겨 보자.

#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

struct TrieNode
{
	map<string, TrieNode> children;
	void insert(TrieNode& node, vector<string>& strs, int idx)
	{
		// 문자열을 모두 넣은 경우
		if (idx == strs.size())
			return;
		string next = strs[idx];
		// 해당 문자열 자식이 없는 경우 생성
		if (!node.children.count(next))
			node.children[next] = TrieNode();
		this->insert(node.children[next], strs, idx + 1);
	}
};

void printRet(TrieNode& root, int depth)
{
	map<string, TrieNode>::iterator it;
	for (it = root.children.begin();it != root.children.end();++it)
	{
		for (int j = 0;j < depth;++j)
			cout << "--";
		cout << it->first << endl;
		printRet(it->second, depth + 1);
	}
}

int main()
{
	int n;
	cin >> n;

	TrieNode trie;
	for (int i = 0;i < n;++i)
	{
		int k;
		cin >> k;
		vector<string> s(k);
		for (int i = 0;i < k;++i)
			cin >> s[i];
		trie.insert(trie,s,0);
	}

	printRet(trie,0);
	return 0;
}

---

참고

• 구종만, 알고리즘 문제 해결 전략, 인사이트(2012), p783-784
• “백준14725 개미굴”, JusticeHui가 PS하는 블로그, 2020년 10월 10일 접속, (https://justicehui.github.io/ps/2019/08/27/BOJ14725/)