[백준 14725] 개미굴

문제 링크 => 14725번: 개미굴 (acmicpc.net)

14725번: 개미굴

 

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

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

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

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

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

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

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

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

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

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

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

 

개미굴의 시각화된 구조를 출력하여라.

개미굴의 각 층을 "--" 로 구분하며, 같은 층에 여러개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.

 

---

 

Trie 자료구조를 활용한 문제이다.

 

먼저 이 문제를 해결하기 위해서 어떻게 해결해야 할지에 대한 접근법을 적어보면 다음과 같다.

 

1. 먹이 정보 갯수와 먹이 정보에 대한 문자열을 받으면 다음과 같이 floor 을 나누기 위해서 '/' 을 삽입한다.

     

     예를 들어서 "3 APPLE BANANA KIWI" 와 같은 먹이 정보가 input 으로 들어왔다고 가정하자.

     그러면 먹이 정보 갯수를 3으로 지정하고 "APPLE/BANANA/KIWI/" 와 같이 문자열을 형성하여 끝 지점과

     시작 지점을 쉽게 구분할 수 있다.

 

2. 위에서 얻은 문자열을 가지고 Trie 를 설정하도록 한다.

    

     위 사진과 같이 root 노드부터 시작하여 문자열 별로 시작 지점과 끝 지점을 marking 해야 한다.

     시작 지점 : 'A'  끝 지점 : 'E'  (=> APPLE)

     시작 지점 : 'B'  끝 지점 : 'A'  (=> BANANA)

     시작 지점 : 'K'  끝 지점 : 'I'   (=> KIWI)

     시작 지점과 끝 지점을 구분하기 위한 boolean 변수 first, finish 를 설정하여 '/' 를 만나면 finish 를 true 로 하고

     '/' 다음 문자 또는 문자열의 첫 문자 를 만나면 first 를 true 로 설정하면 된다. 

 

3. 세팅된 Trie 를 가지고 결과를 출력하는 경우 2가지 조건을 고려해야 한다.

     다음과 같은 경우가 존재한다고 해보자.

 

 

     "APPLE/BANANA/KIWI" 정보와 "APP/HELLO" 정보가 들어온다고 하자.

     이 문제는 사전 순서로 출력을 해야 하기 때문에 APP 다음에 APPLE 이 나와야 하는 사실을 알아야 한다.

     또한 APPLE 중간에 'P' 가 끝 지점인 것 또한 염두해야 한다.

     따라서 중간 지점에 끝 지점인 경우까지 처리하기 위해서 다음과 같이 처리해야 한다.

 

1. finish 지점일 경우 (ex : "APP") :

(1) 먼저 새로운 문자열 처리 ("HELLO")를 위해 floor 값을 2 증가시킨 값과 그 다음 문자가 존재할 경우에

       해당 문자의 first 가 true 일 경우, 문자열을 늘린 후("H") floor 값과 문자열을 인자값으로 그 다음 문자로 

       이동한다.

(2) "APP" 다음의 사전 정보("APPLE")가 있을 경우를 대비하기 위해 그 다음 문자가 존재할 경우에 해당 문자의

       first가 true 가 아닐 경우, 문자열을 늘린 후 그 다음 문자로 이동한다. (floor는 유지)

 

2. finish 지점이 아닐 경우 (ex : "BANA", "KI", "APPL"):

     그 다음 문자가 존재할 경우에 해당 문자의 first 가 true 가 아닐 경우, 문자열을 늘린 후 그 다음 문자로

     이동한다. (floor 는 유지)

 

 

Solution Code     

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string>

using namespace std;

struct Trie* make_child();

struct Trie {
	Trie* child[26];
	bool first, finish;

	void set_Trie(const char* sentence, bool op) {
		if (*sentence == '\0')
			return;
		if (*sentence == '/') {
			finish = true;
			set_Trie(sentence + 1, true);
		}
		else {
			if (child[*sentence - 'A'] == NULL) 
				child[*sentence- 'A'] = make_child();
			child[*sentence - 'A']->first = op;
			child[*sentence - 'A']->set_Trie(sentence + 1, false);
		}
	}

	void print_Trie(int floor, char sentence[], int length) {
		if (finish) {
			// 출력 처리
			for (int i = 0; i < floor; i++) printf("-");
			printf("%s\n", sentence);

			// 사전순 처리 (APPLE 중에 APP 다음 사전정보 처리)
			for (int i = 0; i < 26; i++) {
				if (child[i] && child[i]->first) {
					char tmp[30];
					tmp[0] = (i + 'A'), tmp[1] = '\0';
					child[i]->print_Trie(floor + 2, tmp, strlen(tmp));
				}
			}
			// 이어질 사전 처리 (APP => APPL => APPLE 처리)
			for (int i = 0; i < 26; i++) {
				if (child[i] && !child[i]->first) {
					sentence[length] = (i + 'A'), sentence[length + 1] = '\0';
					child[i]->print_Trie(floor, sentence, strlen(sentence));
				}
			}
		}
		else {
			// 이어질 사전 처리 (BAN => BANA => BANAN 처리)
			for (int i = 0; i < 26; i++) {
				if (child[i]) {
					sentence[length] = (i + 'A'), sentence[length + 1] = '\0';
					child[i]->print_Trie(floor, sentence, strlen(sentence));
				}
			}
		}
	}

	void clear() {
		first = finish = false;
		for (int i = 0; i < 26; i++)
			child[i] = NULL;
	}
};

Trie* make_child() {
	Trie* ret;
	ret = (Trie*)malloc(sizeof(Trie));
	ret->clear();
	return ret;
}

Trie* root;

void input() {
	int n, idx, total_length;
	char* sentence[20], tmp_sentence[300], full_sentence[300], * ptr;

	fgets(tmp_sentence, 300, stdin);

	ptr = strtok(tmp_sentence, " ");
	n = 0, idx = 0;
	while (ptr != NULL) {
		if (n == 0) n = atoi(ptr);
		else sentence[idx++] = ptr;
		ptr = strtok(NULL, " ");      
	}

	total_length = 0;
	for (int i = 0; i < n; i++) {
		int length = strlen(sentence[i]);
		if (i == n - 1) length -= 1;
		for (int j = 0; j < length; j++) 
			full_sentence[total_length + j] = sentence[i][j];
		full_sentence[(total_length += length)] = '/';
		total_length += 1;
	}
	full_sentence[total_length] = '\0';

	root->set_Trie(full_sentence, true);
}

int main() {
	int n;
	char tmp[30];
	scanf("%d", &n);
	getchar();

	root = make_child();
	for (int i = 0; i < n; i++) input();
	
	for (int i = 0; i < 26; i++) {
		if (root->child[i]) {
			tmp[0] = (i + 'A'), tmp[1] = '\0';
			root->child[i]->print_Trie(0, tmp, strlen(tmp));
		}
	}

	return 0;
}