백준 BOJ 7432 - 디스크 트리

트라이 자료구조를 사용하는 문제.

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

7432번: 디스크 트리

\ 기호를 기준으로 문자열을 토큰화 해서,

이 토큰화된 문자열들이 들어가는 trie 자료구조를 만들어 준다음

얘를 dfs로 순회하면서 출력해주면 정답을 받을 수 있다.

trie 자료구조에 저장할때 std::map을 사용했는데

자동으로 정렬되면서

각 서브 디렉토리는 사전순으로 출력해야 하며,

를 충족시킬 수 있다.

 

#include <bits/stdc++.h>
using namespace std;

struct trie{
	map<string,trie*> child;
	
	void insert(vector<string> &v, int idx){
		if(v.size() > idx){
			string nxt = v[idx];
			if(child.find(nxt) == child.end()) child[nxt] = new trie;
			child[nxt]->insert(v, idx+1);
		}
		return;
	}
	
	void dfs(int space){
		for(auto k : child){
			for(int i=0; i<space; i++) cout << " ";
			cout << k.first << "\n";
			
			k.second->dfs(space+1);
		}
	}
}g;


int main(){
	int n;
	string input;
	string token;
	vector<string> v;
	cin >> n;
	for(int i=0; i<n; i++){
		v.clear();
		token = "";
		cin >> input;
		for(auto k : input){
			if(k == '\\'){
				v.push_back(token);
				token = "";
			}
			else{
				token += k;
			}
		}
		v.push_back(token);
		g.insert(v, 0);
	}
	
	g.dfs(0);
	return 0;
}

깔끔하게 AC.