[G3] 백준 14725번 개미굴 C++ 트라이, 문자열

리뷰

 

문자열을 트리 형태로 관리하여 효율적으로 저장, 출력하기 위한 트라이의 기본이 되는 문제

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

 

전역 변수

• Trie : 문자열을 트리 형태로 저장하는 구조체, 맵을 통해 문자열을 key로, 하위 트라이를 value로 가진다.

 

함수

1. insert

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

 

1. 문자열 트리의 현재 노드에 하위 노드를 삽입하는 함수
2. 현재 노드 정보와 추가해야할 음식들을 문자열 타입 벡터 매개변수로 받는다.
3. 우선 루트 노드 정보를 cur이라는 변수에 포인터를 참조하여 값을 별도로 저장해 준다.
4. 추가할 음식들을 탐색하면서 현재 루트 로드에 해당 음식이 존재하지 않으면 새로운 자식을 추가해 준다.
5. 만약 루트 로드에 존재한다면 cur은 해당 음식의 노드로 이동하게 된다. (존재 하지 않아도 새로 생성된 노드로 이동)
6. foods에 저장된 모든 음식이 저장되도록 트리의 하위노드로 이동하며 추가해 준다.

2. dfs

void dfs(Trie* node, int level)

 

1. 트리를 깊이 우선 탐색을 통해 탐색하며 재귀 레벨에 따라 각 노드 정보를 출력해 주는 함수
2. 트리는 map으로 구성되어 있기 때문에 자동으로 오름차순 정렬되어 있다.
3. 트리의 왼쪽부터 깊이 탐색을 하고 재귀 레벨 level에 따라 --를 붙여 음식 이름을 출력해 준다.

 

문제풀이

1. n값을 입력 받고, 트라이의 루트 노드를 트라이 구조체 타입 변수 root에 초기화해 준다.
2. n번의 반복문을 순회하며 깊이 정보를 a에 받은 후 음식을 저장할 문자열 벡터를 a크기로 초기화 한다.
3. 이후 a번의 반복문을 순회하며 foods벡터에 음식 정보를 입력 받아준다.
4. insert함수를 통해 root로드로 부터 a개의 음식 정보를 foods를 통해 트리를 최신화 해준다.
5. 모든 insert작업을 마친 후 dfs를 통해 트리 정보를 깊이 우선 탐색으로 출력해 준다.

 

참고 사항

• 먹이 정보는 알파벳 대문자로만 이루어져 있다.
• map자료구조를 사용했으므로 같은 깊이의 경우 자동으로 사전 순서로 정렬되어 있다.

 

정답 코드

#include<iostream>
#include<map>
#include<vector>

using namespace std;
struct Trie {
	map<string, Trie*> child;
};

void insert(Trie* node, const vector<string>& foods) {
	Trie* cur = node;
	for (const string& food : foods) {
		if (cur->child.find(food) == cur->child.end()) cur->child[food] = new Trie();
		cur = cur->child[food];
	}
}

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

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

	int n; cin >> n;
	Trie* root = new Trie();
	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		vector<string> foods(a);
		for (int j = 0; j < a; j++) cin >> foods[j];
		insert(root, foods);
	}
	dfs(root, 0);
}