[백준 7432] 디스크 트리 (C++)

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

문제

---

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

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

 

입력

---

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

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

 

출력

---

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

 

 

문제 풀이

---

트라이 문제.

 

문자열과 그 문자열을 데이터로 갖는 트라이를 자식 노드로 갖는 트라이를 구현해주면 된다. map<string, trie*> 자료구조를 생성해 자식 노드들의 정보를 저장한다.

문자를 저장하는 트라이와 마찬가지로 재귀적으로 삽입한다. 자식 노드 map에 특정 문자열이 없다면 트라이를 하나 생성한 후 해당 트라이에 다음 문자열을 삽입하고, 존재한다면 해당 문자열을 가리키는 트라이에 다음 문자열을 삽입한다.

출력은 dfs를 사용하면 된다. 삽입과 마찬가지로 재귀적으로 map을 순차 탐색하며 해당 자식 노드 데이터를 출력한 후, 탐색 함수를 호출해주면 된다.

 

아래는 코드. 

#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <sstream>
using namespace std;

struct trie
{
	map<string, trie*> childs;
	map<string, trie*>::iterator it;

	void insert(queue<string> q)
	{
		if (q.empty())
		{
			return;
		}
		string directoryName = q.front();
		q.pop();
		it = childs.find(directoryName);
		if (it == childs.end())
		{
			trie* newDirectory = new trie();
			childs.insert({ directoryName, newDirectory });
			newDirectory->insert(q);
		}
		else
		{
			it->second->insert(q);
		}
	}

	void dfs(int depth)
	{
		for (it = childs.begin(); it != childs.end(); it++)
		{
			for (int i = 0; i < depth; i++)
			{
				cout << " ";
			}
			cout << it->first << "\n";
			it->second->dfs(depth + 1);
		}
	}
};

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

	int N;
	string str, token;
	trie* root = new trie();
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> str;
		istringstream ss(str);
		queue<string> fullDirectory;
		while (getline(ss, token, '\\'))
		{
			fullDirectory.push(token);
		}
		root->insert(fullDirectory);
	}
	root->dfs(0);
	return 0;
}