[G3] 백준 7432번 디스크 트리 C++ 트라이, 문자열, DFS

리뷰

 

개미굴과 유사한 부분이 많은 문제인듯 하다. 하지만 개미굴과 달리 공백이 아닌 역슬래시로 문자열을 구분

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

 

전역 변수

• n : 디렉토리 전체 경로의 개수
• Trie : 맵을 사용하여 디렉토리 정보를 트라이로 사용할 구조체

 

함수

1. insert

void insert(Trie* node, const vector<string>& strs)

 

1. 트라이에 디렉토리 문자열을 추가할 함수
2. 입력할 디렉토리 이름을 벡터형식으로 입력 받는다.
3. 루트노드에서 부터 시작하여 각 문자열을 하위 요소에 넣어준다.
4. 만약 처음으로 정의된 디렉토리인 경우 새롭게 할당해주고 이동하는 작업을 해준다.

 

2. dfs

void dfs(Trie* node, int level)

 

1. 깊이 우선 탐색을 통해 디렉토리 정보를 출력해 주는 함수
2. map 자료구조 특성상 오름차순으로 정렬이 되어 있기 때문에 깊이 우선 탐색 시 자동으로 정렬되어 있다.
3. 루트 노드로 부터 시작하여 map을 순회하며 값이 존재하면 해당 값을 출력하고 재귀를 진행한다.
4. 이때 각 재귀단계에 맞게 디렉토리 명 앞에 공백을 추가해 주어야 한다.

 

문제풀이

1. n값을 입력 받고 n개의 디렉토리 정보를 입력 받는다.
2. \를 기준으로 문자열을 구분하여 문자열 벡터인 dir에 추가해 준다.
3. insert함수를 통해 root노드로 부터 dir에 존재하는 문자열을 디렉토리로 추가해 준다.
4. 추가 작업이 완료된 후 dfs함수를 호출하여 디렉토리 정보를 사전순으로 출력한다.

 

참고 사항

역슬래시(\)로 구분되기 때문에 입력 문자열을 stringstream으로 변환 하여 getline을 통해 \를 기준으로 구분해 주었다.

문자열에서 역슬래시를 나타내기 위해선 \\로 명시해 주어야 한다.

 

 

정답 코드

#include<iostream>
#include<map>
#include<string>
#include<sstream>
#include<vector>

using namespace std;

int n;
struct Trie {
	map<string, Trie*> child;
};

void insert(Trie* node, const vector<string>& strs) {
	Trie* cur = node;
	for (const string& str : strs) {
		if (!cur->child[str]) cur->child[str] = new Trie();
		cur = cur->child[str];
	}
}

void dfs(Trie* node, int level) {
	Trie* cur = node;
	
	for (const auto& val : cur->child) {
		for (int i = 0; i < level; i++) cout << " ";
		cout << val.first << "\n";
		dfs(val.second, level + 1);
	}
}

Trie* root = new Trie();

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

	cin >> n;
	while (n--) {
		string s; cin >> s;
		stringstream ss(s);
		vector<string> dir;
		while (getline(ss, s, '\\')) dir.push_back(s);
		insert(root, dir);
	}
	dfs(root, 0);
}