[백준 14725번 C/C++] 개미굴

 

[백준 14725번 C/C++] 개미굴

 

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

14725번: 개미굴

---

 

해결전략

 

Tree 트리

Trie  트라이 자료구조

---

 

정답 코드

 

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

int n; // 먹이의 정보 개수
int k; // 먹이 사슬의 길이

struct Node{ // 노드를 표현하는 구조체
private:
	map<string, Node*> child; // 자식 노드를 가리키는 포인터를 담고 있는 map

public:
	void Insert(vector<string>& v, int idx) // 노드를 삽입하는 함수
	{
		if (idx == v.size()) return;

		if (child.find(v[idx]) == child.end()){
			child[v[idx]] = new Node();
		}
		child[v[idx]]->Insert(v, idx + 1); // 재귀 호출
	}

	void PrintTree(int depth)  // 트리를 출력하는 함수
	{
		for(auto& iter : child){
			for (int i = 0; i < depth; i++) {
				cout << "--";
			}
			cout << iter.first << "\n";
			iter.second->PrintTree(depth + 1); // 재귀 호출
		}
	}
};

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

	Node* root = new Node; // 루트 노드 생성

	cin >> n;
	for(int i = 0; i < n; i++)
	{
		cin >> k;
		vector<string> v(k, ""); // 먹이 사슬 정보를 담을 벡터 생성

		for(int j = 0; j < k; j++){
			cin >> v[j];
		}

		root->Insert(v, 0); // 먹이 사슬 정보를 트리에 삽입
	}

	root->PrintTree(0); // 트리 출력

	return 0;
}

 

 

---