boj, 백준) 14725. 개미굴 ( C++ )

1. 문제 링크

www.acmicpc.net/problem/14725

14725번: 개미굴

2. 문제 개요

개미 로봇이 개미굴을 탐사하면서 보내온 신호를 토대로 개미굴의 구조를 파악하는 프로그램을 작성하기.

(문제가 복잡해서 링크를 타고 들어가서 읽어보는 걸 추천합니다.)

3. 문제 힌트

트라이를 구현해보자.(트라이에 대한 기본 지식이 있어야 함)

 

그리고, 자식노드를 만들 텐데 정렬을 편하게 하기 위해 map을 사용해보자.

 

4. 문제 풀이

이 문제는 알고리즘 뿐만아니라 C++에 대한 기초 지식도 필요하다.

우선 트라이를 다루기 위해 C++의 동적할당 방법 등도 알아야 한다.

 

큰 틀로 이 문제를 보면,

하나의 노드(Trie)에 자식들이 있는데, 해당 자식들은 고유한 String을 가지고 있다.

그리고 이 자식(Trie)들을 부모가 갖고 있어야 하는데 이것은 포인터로 갖고 있게 된다.

 

그래서, map<string, Trie*>와 같은 map을 하나의 노드에 갖고 있어야 한다.

입력을 보고, 해당 string이 존재 한다면, 해당 string의 자식으로 이동해서 다음 단어를 삽입하면 된다.

그리고 해당 string이 존재하지 않는다면, 새로운 Trie 노드를 만들고, 만든 Trie노드에 다음 단어를 삽입하면 된다.

 

map은 default가 오름차순이기 때문에 key값인 string을 오름차순으로 자동으로 정렬해준다.

그래서 iterator로 map을 모두 순회하면서 dfs처럼 낮은 인덱스부터 방문하면 된다.

 

 

크게 보면 문제는 간단한데 어떻게 구현을 해야 할지 잘 몰라서 어려운 문제 같다.

트라이를 응용할 줄 알아야 하기 때문에...

 

 

5. 코드

#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;


struct Trie {
	
	Trie(){}
	~Trie() {
		for (map<string, Trie*>::iterator iter = m.begin(); iter != m.end(); ++iter)
			delete (*iter).second;
	}

	void insert(vector<string>  &v, int index) {

		if (v.size() == index)
			return;

		if (m.find(v[index]) == m.end())
		{
			m.insert({ v[index], new Trie() });
			m[v[index]]->insert(v, index + 1);
		}
		else
		{
			m[v[index]]->insert(v, index + 1);
		}
	}

	void find(int depth) {
		for (map<string, Trie*>::iterator iter = m.begin(); iter != m.end(); ++iter) {

			for (int i = 0; i < depth; ++i)
				cout << "--";
			cout << (*iter).first << '\n';

			(*iter).second->find(depth + 1);
		}
	}
	map<string, Trie*> m;
};

int n;

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

	cin >> n;
	Trie * root = new Trie();

	for (int i = 0; i < n; ++i) {
		int k;
		cin >> k;
		vector<string> v(k);

		for (int j = 0; j < k; ++j) 
			cin >> v[j];

		root->insert(v, 0);		
	}
	root->find(0);
	delete root;
	return 0;
}

 

 

6. 결과