[백준][C++] 14725: 개미굴

문제 링크: https://www.acmicpc.net/problem/14725

 

음... 어떻게 풀까 고민을 좀 했는데요, 간단하게 트라이의 노드를 map<string, 인덱스>로 만들면 됩니다. N, K 조건이 빡빡하지 않기 때문에 적당히 풀면 됩니다

여기서 map의 value를 인덱스를 쓸지, 포인터를 쓸지는 뭐 구현하는 사람 마음입니다. 저는 요즘 트라이를 배열로 짜는 연습중이라 배열로 만들었습니다.

 

출력은 preorder로 짜면 됩니다. root는 빼고 나머지만 출력하면 됩니다.

std::map은 기본적으로 비내림차순으로 정렬된 상태고, iterator를 써서 순회하면 비내림차순으로 순회하게 됩니다.

#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;


map<string, int> trie[15001];	// name, next_idx
int trie_size;

void trie_insert(const vector<string>& vs) {
	int node = 0;
	for (auto& s : vs) {
		if (trie[node].find(s) == trie[node].end()) {
			trie[node][s] = ++trie_size;
			node = trie_size;
		}
		else
			node = trie[node][s];
	}
}

void print_trie(int node, int depth) {
	for (auto& [s, i] : trie[node]) {
		cout << string(depth * 2, '-') << s << '\n';
		print_trie(i, depth+1);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	int n;
	cin >> n;
	while (n--) {
		int k;
		cin >> k;
		vector<string> vs(k);
		for (auto& s : vs)
			cin >> s;

		trie_insert(vs);
	}
	print_trie(0, 0);
	
	return 0;
}

배열로 짠 트라이로 구현한 코드입니다. 노드 개수 상한은 N*K=15000 거기에 루트 + 1=15001로 설정했습니다.

 

맞은사람 코드를 보다 보니 배열로 짜는것보다 훨씬 깔끔하면서 메모리도 덜쓰고, 동적할당은 하지 않는 어썸한 코드가 있어서 링크를 남깁니다

저보다 훨씬 깔끔한 코드(shiftpsh님 코드): https://www.acmicpc.net/source/17311258