백준 개미굴 14725

백준 개미굴 14725

백준 개미굴 문제의 경우 전형적인 trie문제이다. trie이란 트리 구조를 활용하여 여러 개의 문자열 중 자신이 갖고 있는 문자열을 찾을 수 있는 알고리즘이다. 

 

hoony-gunputer.tistory.com/entry/%ED%8A%B8%EB%9D%BC%EC%9D%B4

트라이

입력되는 문자열을 기준으로 layer을 구성해서 출력하는 문제이다. 이문제에서 체크해주어야 하는 상황은 몇가지가 있다. 

 

1. 이 문자의 시작이 첫 시작이라면 
--을 출력해주어야 하기 때문에 체크해주어야 한다. 

 

2. 입력되는 문자열이 base를 기준으로 몇번째로 떨어져있는지 체크

 

3. 이미 터미널인 것을 체크했지만 같은 layer일 경우 

원래 이 경우에는 답으로 체크되었다가 데이터가 추가되며 틀려서 수정하게 되었다. 

 

A A

A ABC

 

이 경우 필자의 경우 terminal을 만나면 자동으로 다른 layer로 체크해서 --을 출력시켰는데 하지만 이럴 경우

A

--A

----BC

가 출력된다. 그 이유는 A를 마지막 값이라고 체크한 다음 레이어가 넘어가기 떄문이다. 

 

해결책: 이 문제를 해결하기 위해 terminal일때 까지 이전의 값을 계속 저장하며 terminal임에도 다음 값이 layer가 같다면 저장된 값을 출력 다르다면 저장된 값을 초기화한다. 이를 반복해주면 문제를 해결할 수 있다. 

 

 

코드

#include <cstdio>
#include <string.h>
#include <string>

using namespace std;

int toNumber(char a){return a - 'A';}
const int ALPHABET = 26;
struct TrieNode{
	bool terminal;
	int layer;
	TrieNode* children[ALPHABET];
	TrieNode():terminal(false){
		layer = -1;
		memset(children, 0, sizeof(children));
	}
	~TrieNode(){
		for(int i = 0; i < ALPHABET; i++)
			if(children[i] != NULL)
				delete(children[i]);
	}

	void insert(const char* key, int nowLayer){
		if(*key == 0){
			terminal = true;
		}
		else{
			int next = toNumber(*key);
			if(layer == -1)  layer = nowLayer;
			if(children[next] == NULL)
				children[next] = new TrieNode();
			children[next]->insert(key+1, nowLayer);
		}
	}

	void allFind(int isStart, int isBase, string base){
		if(terminal)
			printf("\n");
		for(int i = 0; i < 26; i++){
			if(children[i] != NULL){
				if(isStart){
					for(int i = 0; i < layer; i++)
						printf("--");
					if(isBase != -1)
					printf("%s", base.c_str());		
				}
				printf("%c", char(i + 'A'));
				if(children[i]->terminal){
					if(layer  == children[i]->layer)
						children[i]->allFind(1, i, base+char(i + 'A'));
					else
						children[i]->allFind(1, -1, "");	
				}
				else
					children[i]->allFind(0, -1, base+char(i + 'A'));	
			}
		}
	}
};

int main(){
	int N, base;
	char feed[100];
	TrieNode *root = new TrieNode();
	scanf("%d", &N);
	for(int i = 0; i < N; i++){
		scanf("%d", &base);
		string allFeed = "";
		for(int i = 0; i < base; i++){
			scanf("%s", &feed);
			allFeed+=feed;
			root->insert(allFeed.c_str(), i);
		}
	}

	root->allFind(0, -1, "");
}