백준 14725번 : 개미굴 (트라이)

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

14725번: 개미굴

 

이 문제를 풀 떄 트라이라는 자료구조를 알고 풀면 더 쉽게 접근이 가능하다.

처음에는 나도 트라이라는 것이 생소해서 공부를 시작하고 풀었다.

그리고 문제를 풀때 다른 사람 코드를 참조했다...(아직 트라이는 어색하다..ㅜㅜ)

트라이란? 

단순히 말해서 트리구조이다. 이걸 문자열에 특화되게 만든게 트라이 라는 것이다.

(처음에는 포인터 부분이 약해 이해가 잘 안되는데 그냥 해당 노드에 들어있는 child에 들어가는 값을 각 층별로 들어있는 값이라 생각하면 된다. )

그리고 내가 공부한 블로그이다. (많은 도움이 되었습니당...)

https://rebro.kr/86

[자료구조] 트라이(Trie) 자료구조

 

 

그럼 다시 본론으로 돌아가서 

이 문제를 풀기 위해

1 . 노드를 설정  (사전순으로 정렬이 필요하기해 Map 자료구조를 이용해서 자동으로 정렬되게 만들었다.)

2. insert 함수를 만들어서 해당 문자열이 있으면 다음 층으로 넘어감  , 문자열이 없으면 새로운 노드를 만들고 연결시킨다.

3. 그리고 출력 방식을 보면 dfs로 탐색을 하는 것을 알 수 있다. 이를 신경써서 dfs 함수 구현

 

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

struct Trie{
	map<string, Trie*> child;
	
	void insert(vector<string> v, int depth) {
		if (depth == v.size()) return;
		string s = v[depth];
        map<string, Trie*>::iterator iter;
		iter = child.find(s);		
		if (iter != child.end()) 		
			iter->second->insert(v, depth + 1);    //해당 문자열이 있으면 다음 층으로 넘어감    
		else {
			Trie* n = new Trie;    //해당 문자열이 없으면 새로운 노드 생성후 연결
			child.insert({ s,n });
			n->insert(v, depth + 1);
		}
	}
	void dfs(int depth) {
		if (child.empty()) return;

		for (auto it = child.begin(); it != child.end(); it++) {  //child는 각 층에 있는 값들 
			for (int i = 0; i < depth; i++)
				cout << "--";
			cout << it->first << '\n';
			it->second->dfs(depth + 1);
		}
	}
};

int main() {
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
     cout.tie(NULL);
	int num, index;
	Trie* root = new Trie;
	string s;
	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> index;
		vector<string> v;
		for (int j = 0; j < index; j++) {
			cin >> s;
			v.push_back(s);
		}
		root->insert(v, 0);
	}
	root->dfs(0);
	return 0;
}