[백준 14725] 개미굴 (C++)

문제링크: www.acmicpc.net/problem/14725

14725번: 개미굴

1. 주의할 점

- 트리나 트라이에 대해서 알고 있어야 한다

- 사전순으로 출력해야한다(정렬된 무엇인가를 사용)

 

2. 구현

- Node 구조체를 만들어서 해당 Node의 Map을 생성하고, insert()와 print()의 기능을 하는 함수를 생성한다

- Node구조체 형태인 Root 노드를 처음에 만든다

- Insert() 함수는 입력받은 길을 저장하고 있는 V 벡터와 현재 개미굴의 층수를 변수로 받는다. 더 이상 경로가 없다면 Return, 해당 층수에 이미 같은 경로가 저장되어 있다면 다음 경로로 이동하고 마지막으로 해당 층수에 같은 경로가 존재하지 않다면 새로운 Node를 만들어서 Map에 저장한 이후, 다음 경로를 Map에 insert한다

- Print() 함수는 DFS()의 형태로, 해당 층수에 알맞는 먹이를 출력하면 된다

 

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

struct Node{
	map<string, Node*> child;
	map<string, Node*>::iterator iter;
	void insert(vector<string> v, int idx) {
		if (idx == v.size()) return;
		string ss = v[idx];
		iter = child.find(ss);		//Node
		if (iter != child.end()) 		//이미 있는 경우
			iter->second->insert(v, idx + 1);
		else {
			Node* n = new Node;
			child.insert({ ss,n });
			n->insert(v, idx + 1);
		}
	}
	void print(int idx) {
		if (child.empty()) return;
		for (auto it = child.begin(); it != child.end(); it++) {
			for (int i = 0; i < idx; i++)
				cout << "--";
			cout << it->first << '\n';
			it->second->print(idx + 1);
		}
	}
};
Node tmp;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int num, val;
	Node* root = new Node;
	string ss;
	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> val;
		vector<string> v;
		for (int j = 0; j < val; j++) {
			cin >> ss;
			v.push_back(ss);
		}
		root->insert(v, 0);
	}
	root->print(0);
	return 0;
}