[백준]7432번 디스크 트리 -C/C++

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

 

7432번: 디스크 트리

문제

갑자기 맥북이 상근이의 손에서 떨어졌고, 화면이 켜지지 않았다. AS센터에 문의해보니 수리비가 97만원이 나왔고, 상근이는 큰 혼란에 빠졌다. 돈도 중요하지만, 상근이는 그 속에 들어있는 파일이 걱정되기 시작했다. 다행히 상근이는 저장되어 있는 중요한 디렉토리의 전체 경로를 텍스트 파일로 따로 저장하고 있었다. 예를 들면, WINNT\SYSTEM32\CERTSRV\CERTCO~1\X86. 

상근이의 중요한 디렉토리의 전체 경로가 모두 주어졌을 때, 디렉토리 구조를 구해 보기 좋게 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 중요한 디렉토리 전체 경로의 개수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개 줄에는 디렉토리 경로가 주어진다. 경로는 한 줄로 이루어져 있으며, 공백을 포함하지 않는다. 경로는 80글자를 넘지 않으며, 디렉토리는 역슬래시(\)로 구분된다.

각 디렉토리의 이름은 1~8글자이며, 알파벳 대문자, 숫자, 특수 문자로 이루어져 있다. 디렉토리 이름에 들어있을 수 있는 특수문자는 !#$%&'()-@^_`{}~ 이다.

출력

디렉토리 구조를 보기 좋게 출력한다. 한 줄에 하나씩 디렉토리의 이름을 출력하며, 공백은 디렉토리 구조상에서 깊이를 의미한다. 각 서브 디렉토리는 사전순으로 출력해야 하며, 부모 디렉토리에서 출력한 공백의 개수보다 1개 많게 공백을 출력한다. 예제 출력을 보면서 형식을 참고하는 것이 좋다.

---

 

 Trie 문제이다.

한 줄이 들어오면 "\"을 기준으로 parsing을 진행한 다음 Trie에 추가하는 방법을 사용하면 된다.

Trie 구조는 노드마다 자신의 string과 자식들의 map 이 있다. 공통되는 부분이 Trie에 존재하지 않을 때까지 내려간 뒤 새로운 부분이 나오면 child map에 원소를 추가한 뒤 해당 노드로 들어가 같은 작업을 반복한다.

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

int n;

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

	void addNode(vector<string>v,int idx) {
		if (idx == v.size()) return;
		auto iter = child.find(v[idx]);
		if (iter != child.end())
			iter->second->addNode(v, idx + 1);
		else {
			Node* n = new Node;
			child.insert({ v[idx],n });
			n->addNode(v, idx + 1);
		}
	}

	void print(int idx) {
		if (child.empty()) return;
		for (auto iter = child.begin(); iter != child.end(); iter++) {
			for (int i = 0; i < idx; i++)
				cout << " ";
			cout << iter->first << "\n";
			iter->second->print(idx+1);
		}
	}
};

vector <string> split(string s, char sep) {
	vector <string> ans;
	stringstream ss(s);
	string tmp;

	while (getline(ss, tmp, sep))
		ans.push_back(tmp);
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	string s;
	Node* root = new Node;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s;
		vector <string> v = split(s,'\\' );
		root->addNode(v,0);
	}
	root->print(0);
	return 0;
}

---

     Trie를 연습할 겸 다른 문제를 풀었다. parsing 하는 부분을 추가한 것 말고는 다른 부분이 없는 것 같다! 너무 유형이 비슷해서 다른 Trie 문제들도 풀어봐야겠다.