백준 / 14725 개미굴

www.acmicpc.net/problem/14725

14725번: 개미굴

트라이 자료구조라는 것을 새로 접하게 되었다. 트라이 자료구조란, string을 트리모양으로 만들어 트리를 탐색하며 string을 만드는 자료구조이다. 

(참고 : twpower.github.io/187-trie-concept-and-basic-problem)

 

위 문제는 트라이 자료구조에 필요한 모든 것을 구할 필요는 없으나, 삽입 함수 정도만 구하면 됩니다. 

 

코드는 다음과 같습니다.

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

using namespace std;

int n, k;
vector<string>foods[1001];

// 자식 노드 담을 구조체
// map 컨테이너의 count : key값 존재하면 1, 없으면 0
// 입력의 순서대로 count==1 이면 거기에 자식 노드 붙힘
// 없으면 새 노드 붙힘
struct Node {
	map<string, Node>child;
};

void init()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> k;
		for (int j = 0; j < k; j++) {
			string s;
			cin >> s;
			foods[i].push_back(s);
		}
	}
}

// vector v의 idx번째 입력을 node에 붙힘
// 해당 string이 없으면 새로 node에 붙힘
// 있으면 그 다음 string에 대해 검사
void insert(Node &node, vector<string>&v, int idx)
{
	// 리프 노드인 경우 (더 이상 붙힐 자식이 없음)
	if (idx == v.size())
		return;

	map<string, Node>::iterator iter;
	bool exit = false;
	for (iter = node.child.begin(); iter != node.child.end(); iter++) {
		if (iter->first == v[idx]) {
			exit = true;
			break;
		}
	}
	if (!exit) {
		node.child[v[idx]] = Node();
	}
	insert(node.child[v[idx]], v, idx + 1);
}

// 트라이에 저장된 거 출력
// map은 기본적으로 오름차순으로 정렬
// 문제에서 사전순으로 출력하라했으므로 기본형 그대로 놔두면 됨
void dfs(Node &node, int depth)
{
	// iterator 안 쓰고 auto i : node.child 이런 식으로 해도 됨
	map<string, Node>::iterator iter;
	for (iter = node.child.begin(); iter != node.child.end(); iter++) {
		for (int idx = 0; idx < depth; idx++) {
			cout << "--";
		}
		cout << iter->first << '\n';
		dfs(iter->second, depth + 1);
	}
}

int main()
{
	init();
	Node root;

	// 입력에 대해 트리(트라이) 만들기
	for (int i = 0; i < n; i++) {
		insert(root, foods[i], 0);
	}

	// 출력
	dfs(root, 0);
}