Trie - ex) BOJ - 14725번 : 개미굴

문자열 관련 문제를 풀 때 C++의 경우 <Set> 또는 <Map>을 사용 및 응용하여 대부분의 문제를 해결할 수 있다. 하지만 트라이 자료구조 또한 필수로 알아야한다. 트라이는 문자열을 효율적으로 처리하기 위한 트리 자료구조이다. 특히 "접두사"와 같은 단어가 문제에 등장하면 트라이를 우선 떠올려도 괜찮을 듯 하다. 

 

트라이

트라이란,

트라이(Trie) : 문자열을 효율적으로 처리하기 위한 트리 자료구조

 

• 단어 S를 삽입/탐색/삭제할 때 모두 O(|S|) (|S|는 문자열 S의 길이)
• 문자열을 그냥 배열에 저장하는 것보다 최대 4 x 글자의 종류배 만큼 더 사용 (예를 들어 각 단어가 알파벳 대문자로만 구성되어 있을 경우(글자의 종류 = 26) 따라서 104배)

이론적인 시간복잡도와는 별개로 실제로는 트라이가 해시, 이진 검색 트리에 비해 훨씬 느리다. 일반적인 상황에서는 해시나 이진 검색 트리를 사용하는게 좋으나 트라이의 성질을 사용해야 하는 문제가 여럿 존재하고 위에서 언급한 "접두사"와 같은 단어가 나왔을 경우이다.

 

아래 코드는 간단한 트라이 자료구조 - insert, find, erase에 대한 구현 코드이다.

현재 준비하는 알고리즘 공부는 대부분 문제에 주어지는 단어의 최대 개수, 길이가 주어지므로 이와 같이 최대 크기 배열을 선언하고 구현하는 것이 구조체 전체를 구현하는 방법보다 빠르고 직관적일 수 있다.

 

단어의 최대 가수, 길이를 알 경우 최대 값 MX를 아래와 같이 구한 뒤 배열의 최대 크기로 지정해주면 된다.

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 1e18 + 3
#define endl '\n'

using namespace std;

const int ROOT = 1;
const int MX = 10000 * 500 + 5;

int unused = 2;
bool chk[MX];
int nxt[MX][26];

void init(){
    for(int i=0;i<MX;i++){
	    fill(nxt[i], nxt[i]+26, -1);
    }
}

int c2i(char c){
	return c - 'a';
}

void insert(string &s){
	int cur = ROOT;
    for(auto c : s){
    	if(nxt[cur][c2i(c)] == -1){
            nxt[cur][c2i(c)] = unused++;
        }
        cur = nxt[cur][c2i(c)];
    }
    chk[cur] = true;
}

bool find(string &s){
	int cur = ROOT;
    for(auto c : s){
    	if(nxt[cur][c2i(c)] == -1) return false;
        cur = nxt[cur][c2i(c)];
    }
    return chk[cur];
}

void erase(string &s){
	int cur = ROOT;
    for(auto c : s){
    	if(nxt[cur][c2i(c)] == -1) return;
        cur = nxt[cur][c2i(c)];
    }
    chk[cur] = false;
}

 

---

 

 

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

14725번: 개미굴

문제

개미는(뚠뚠) 오늘도(뚠뚠) 열심히(뚠뚠)  일을 하네.

개미는 아무말도 하지 않지만 땀을 뻘뻘 흘리면서 매일 매일을 살길 위해서 열심히 일을 하네.

한 치 앞도(뚠뚠) 모르는(뚠뚠) 험한 이 세상(뚠뚠) 그렇지만(뚠뚠) 오늘도 행복한 개미들!

우리의 천재 공학자 윤수는 이 개미들이 왜 행복한지 궁금해졌다.

행복의 비결이 개미가 사는 개미굴에 있다고 생각한 윤수는 개미굴의 구조를 알아보기 위해 로봇 개미를 만들었다.

로봇 개미는 센서가 있어 개미굴의 각 층에 먹이가 있는 방을 따라 내려가다 더 이상 내려갈 수 없으면 그 자리에서 움직이지 않고 신호를 보낸다.

이 신호로 로봇 개미는 개미굴 각 층을 따라 내려오면서 알게 된 각 방에 저장된 먹이 정보를 윤수한테 알려줄 수 있다.

로봇 개미 개발을 완료한 윤수는 개미굴 탐사를 앞두고 로봇 개미를 테스트 해보기 위해 위 그림의 개미굴에 로봇 개미를 투입했다. (로봇 개미의 수는 각 개미굴의 저장소를 모두 확인할 수 있을 만큼 넣는다.)

다음은 로봇 개미들이 윤수에게 보내준 정보다.

• KIWI BANANA
• KIWI APPLE
• APPLE APPLE
• APPLE BANANA KIWI

(공백을 기준으로 왼쪽부터 순서대로 로봇 개미가 각 층마다 지나온 방에 있는 먹이 이름을 뜻한다.)

윤수는 로봇 개미들이 보내준 정보를 바탕으로 다음과 같이 개미굴의 구조를 손으로 그려봤다.

APPLE
--APPLE
--BANANA
----KIWI
KIWI
--APPLE
--BANANA

(개미굴의 각 층은 "--" 로 구분을 하였다.

또 같은 층에 여러 개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.)

우리의 천재 공학자 윤수는 복잡한 개미굴들을 일일이 손으로 그리기 힘들어 우리에게 그려달라고 부탁했다.

한치 앞도 모르는 험한 이세상 그렇지만 오늘도 행복한 개미들!

행복의 비결을 알기 위해 윤수를 도와 개미굴이 어떤 구조인지 확인해보자.

---

[풀이과정] 

 

문제를 잘 읽어보면 트리 구조로 구현해야하는 것은 알겠는데 어떻게 구현해야할까 감이 잘 안온다. 문자열에 존재하는 하나 하나의 각 단어를 노드로 표현했던 위 트라이 구현과는 달리 이 문제는 하나의 단어가 아닌 하나의 문자열이 노드가 되어야한다. 그럼 각 단어로 연결과정을 표현했던 int nxt[MX][26]과 다르게 문자열로 저장할 수 있게 해주면 된다. 그리고 출력을 할 때 사전 순으로 출력해야하기 때문에 알아서 정렬이 될 수 있도록 map으로 저장해주면 된다.

 

int nxt[MX][26] -> map<string, int> nxt[MX];

 

위와 같이 달리 해주고 똑같이 각 노드의 정보는 unused값으로 저장하기 때문에 int형으로 저장된다.

root는 1, 그 아래 최초로 오는 것은 2 등등 이렇게 된다.

 

따라서 번호를 이용하여 dfs를 수행하면 출력할 수 있다.

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 1e18 + 3
#define endl '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int N, M;
const int ROOT = 1;
const int MX = 10000 * 15 + 5;
int unused = 2;
bool chk[MX];
map<string, int> nxt[MX];

void insert(vector<string> &s){
	int cur = ROOT;
	for(auto c : s){
		if(!nxt[cur][c]) {
			nxt[cur][c] = unused++;
		}
		cur = nxt[cur][c];
	}
}

void input(){
	cin >> N;
	while(N--){
		cin >> M;
		vector<string> inputStr(M);
		for(int i=0;i<M;i++){
			cin >> inputStr[i];
		}
		insert(inputStr);
	}
}

void dfs(int cur, int d){
	for(auto nx : nxt[cur]){
		string level;
		for(int i=0;i<d;i++) level += "--";
		cout << level << nx.first << endl;
		dfs(nx.second, d+1);
	}
}

void solution(){
	dfs(1, 0);
}

int main(){
	fastio;
	input();
	solution();

	return 0;
}