[BOJ / 트라이] 14725 개미굴

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

14725번: 개미굴

 

14725 개미굴

알고리즘 : 자료구조, 트라이, 맵

맵은 레드블랙트리 기반으로 이루어진 자료구조이기에 자동으로 내부정렬이 됩니다. 이 문제에서는 정렬을 하여 자식들을 출력하여야 되는 트라이 구조이기 때문에 맵을 사용하여 자식들을 관리하면 됩니다. 

 

 

 

< CODE >

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

using namespace std;

struct Node {
	string str;
	Node * par;
	map<string, Node*> child;

	Node() {

	}
};

Node* root;

Node * init(string keyword, Node * par) {
	Node * node = new Node();
	node->str = keyword;
	node->par = par;
	par->child[keyword] = node;

	return node;
}

void dfs(Node * now, int depth) {
	for (auto a = now->child.begin(); a != now->child.end(); a++) {
		for (int i = 0; i < depth; i++)
			cout << "--";
		cout << a->second->str << '\n';
		dfs(a->second, depth + 1);
	}
}

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

	root = new Node();
	root->str = "root";
	root->par = nullptr;

	int n;

	cin >> n;

	for (int i = 0; i < n; i++) {
		int cnt;
		Node* last = root;

		cin >> cnt;

		while (cnt--) {
			string a;

			cin >> a;
			
			if (last->child.find(a) != last->child.end())
				last = last->child[a];
			else{
				Node* newChild = init(a, last);
				last = newChild;
			}
		}
	}

	dfs(root, 0);

	return 0;
}

시간 : 0ms

 

태그 : #14725 개미굴 #BOJ 개미굴