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

문제 링크

14725번: 개미굴

문제 요약

로봇이 개미가 굴을 타고 들어가면서 찾게 된 먹이 정보가 주어진다. 이 먹이정보를 바탕으로 개미굴의 형태를 출력해야 한다.

접근 방법

백준 단계별로 풀어보기의 '문자열 알고리즘 1'에서 KMP만 공부하고 문자열은 더 안 보고 있었는데, 간만에 새로운 걸 배워봤습니다. 이 문제는 트라이라는 자료구조를 통해서 풀었습니다.

먼저 구조체를 하나 선언해두는데, 이 구조체 내에는 맵이 있고, 맵의 key는 문자열, value는 구조체 포인터입니다. 자식 노드를 연결할 때, 구조체를 new 연산자를 통해서 생성해주고 포인터 변수에 연결해 준 다음에 포인터 변수를 맵에 넣어줍니다. 굳이 map을 사용하는 이유는 map은 내부에서 자동적으로 정렬을 해주기 때문에, 사전순으로 출력하기 위함입니다.

이제 로봇이 탐색 과정에서 만난 요소들을 삽입하고자 한다면, 요소들을 벡터에 저장하고 재귀호출을 통해서 삽입을 해줍니다. 현재 인덱스의 문자열이 map 내부에 있다면 key에 대응되는 value를 바로 재귀호출을 해주고, 없다면 자식 노드를 생성해 연결해주고 재귀호출해줍니다.

원소들을 출력할 때는 통상의 DFS와 비슷하게 접근해주면 됩니다. 출력이 끝난 노드들은 모두 delete로 지워줍니다.

코드

#include <bits/stdc++.h>

using namespace std;

struct Trie {
	map<string, Trie*> m;

	void insert(vector<string>& v, int idx) {
		if (idx == v.size())
			return;

		if (m.find(v[idx]) == m.end()) {
			Trie* trie = new Trie;
			m.insert({ v[idx], trie });
		}

		m[v[idx]]->insert(v, idx + 1);
	}

	void dfs(int d) {
		for (auto& i : m) {
			for (int j = 0; j < d; j++)
				cout << "--";
			cout << i.first << '\n';
			i.second->dfs(d + 1);
			delete i.second;
		}
	}
};

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

	int n;
	cin >> n;

	Trie* root = new Trie;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;

		vector<string> v(num);
		for (int j = 0; j < num; j++)
			cin >> v[j];
		root->insert(v, 0);
	}

	root->dfs(0);
	delete root;
	return 0;
}