문제

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

입력

첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000)

두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정보 개수 K가 주어진다. (1 ≤ K ≤ 15)

다음 K개의 입력은 로봇 개미가 왼쪽부터 순서대로 각 층마다 지나온 방에 있는 먹이 정보이며 먹이 이름 길이 t는 (1 ≤ t ≤ 15) 이다.

출력

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

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

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

풀이

string으로이루어진 Trie자료구조를 만들어서
내부적으로 DFS를 돌려서 출력하는 문제이다.
이전까지 Trie구조는 문자하나의 아스키코드값을 저장하기만해서
Trie* node[256]등으로 포인트배열이 nullptr이 아니면 존재하는것으로 판별했으나, 이번문제는 string을 하나의 노드로 둬야하므로
내부적으로 map객체를 생성해서 저장했다.
map객체의 key로 string을, value를 Trie포인터로 두어서 아래와 같은 그림이 그려지게된다.

이렇게 Trie자료구조의 내부구조가 형성되는 과정을 살펴보
자.

0. 사용될 Trie자료구조의 모습
   이 코드를 바탕으로 그림을 그려보았다.
   
   
   
   

1. line89 : 서로 연결된 string벡터를 전달받고 root를 가리키는 cur포인터를 생성하는 모습이다.
Trie객체는 내부에 map객체를 포함하므로 실선으로 표현한 모습이다.

2. line92 : 전달받은 string중 첫번째를 확인한다. "KIWI"가 cur포인터가 가리키는 Trie객체 내부의 map객체에 없다.

3. line95 : map에 "KIWI"를 키값으로 넣고 그에 해당하는 밸류로 새로운 Trie객체를 생성한다. 그림에서 new Trie()가 생성한객체고 1번과 같은방법으로
내부에 빈 map객체를 가지고있다.
이떄 "KIWI"키에해당하는 밸류값이 새로 생성한 개체를 가리킨다.
line 96 : cur포인터가 "KIWI"가 가리키는 대상을 따라간다.
즉 cur은 새로생성된 Trie객체를 참조하게된다.!

4. line90 : 다음 string을 확인한다.

5. line92 : cur가가리키는 map객체에 "BANANA"키가 없으므로 3번과정처럼 새롭게 객체를 생성(line95)하여 "BANANA"키의 밸류인 포인터가 생성한 객체를 가리키게 한다.

6. line96 : cur포인터가 새로생성한 Trie객체를 가리킨다.

그리고 처음 입력받은 string벡터에 다음요소가 없으므로 종료한다.





7. 이번엔 새롭게 길이가 2인 string벡터를 전달받았다.
새로 insert가 호출되었으므로 cur객체는 자기자신인 trie(root)객체를 가리키고있으며 trie는 내부에 비어있는 map객체를 가지고있다.

8. 이제 line92가 거짓이므로("KIWI"키가 존재하므로), 새롭게 객체를 생성하지않고 cur포인터가 생성되있는 객체를 따라간다.
이렇게 가리키게 될것이다. 다음 string을 확인하자.

9. "APPLE"키가 존재하지않으므로 cur가 가리키는 map객체에 키를 추가하며 동시에 밸류로 새로운 객체를 만들어 가리키게(주솟값을 가지게)한다.

10. 마지막으로 cur포인터가 이동한다. 이제 insert가 전달받은 vector내의 string을 모두 추가했으니 종료한다.

11. Insert함수에 길이가 2인 string vector가 들어왔다. cur포인터를 생성하고 vector의 첫요소인 "APPLE"을 확인한다.

12. cur가 가리키는 map객체에 "APPLE"키가 없으니 추가하고 새롭게 객체도 생성했다.
또, cur포인터도 생성한 객체를 따라갔다.

13. 이번에도 "APPLE"키가 없다.
14. 키를 추가하고 객체를 생성하고 cur포인터가 이동했다.
vector가 비었으니 insert함수를 종료한다.

15. 새로 insert()가 호출된상태다. "APPLE"이 존재하므로 cur가 가리키는 대상만 바뀔것이다.

16. cur가 가리키는 map객체에 "BANANA"가 없으므로 새로 생성하게 될것이다.

17. 새로 객체를 생성하며, cur포인터도 변경되었다.
마지막으로 "KIWI"가 cur포인터가 가리키는 map객체에 없으니 또한번 객체를 생성할것이다.

18. 최종적으로 총 세번의 insert함수가 완료된후 Trie자료구조의 상태도이다.

이를 좀더 보기 편하게 수정하면 아래와 같아진다.
여기서 각각 사각형이 하나의 Trie객체에 있는 map 객체가된다.
이렇게 나타내니 문제에서 보여준 개미굴과 모습이 비슷해보인다.

0번에서 보여준 우리의 코드는 지금껏 설명한 과정대로 string을 내부적으로 Trie자료구조 형태로 보관한다.

struct Trie {
	map<string, Trie*> node; //key로 문자열, value로 포인터를가짐

	//비 재귀방법으로 트라이구조를 만듬
	void insert(vs &list) {
		Trie* cur = this;
		rep(i, sz(list)) {
			//키에 해당하는 value가 있는지 확인
			if (cur->node[list[i]] == nullptr) 
				//없으면 키에대한 value를 지정해줌
				//(새로운 객체를 생성해줌 => 포인터가 새로운 객체공간을 가리킴)
				cur->node[list[i]] = new Trie(); 
			cur = cur->node[list[i]];
		}
	}
};

두번째로 구성된 Trie구조에서 DFS를 돌린결과를 출력해야하는데,
외부에서 DFS함수를 구성해도되지만 보기 편하게 Trie구조체에서 구현했다.

이는 맵객체에 string과 그 포인터를 저장함을 적극 활용했다.
문제에서 string출력시 그 깊이만큼 '--' 문자를 출력하라했으니
DFS의 인자로 그 깊이를 전달하도록 코드를 짯다.
중요한점은 포인터를 통해방문한 Trie객체에 존재하는 map객체내의 string을 출력후 그 포인터로 DFS를 또 호출하는것...
말로 설명하려니 더 어려워보인다. 코드에 익숙해지자.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
#define mp std::make_pair 
#define mt std::make_tuple
#define dq std::deque
#define pq std::priority_queue
#define sw std::swap
#define ts(x) std::to_string(x)
#define tc() c_str()
#define sc(x, ...) scanf(x, ##__VA_ARGS__) 
#define pr(x, ...) printf(x, ##__VA_ARGS__) 
#define ins(x) insert(x)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define PB() pop_back()
#define PF() pop_front()
#define ph(x) push(x)
#define TT() top()
#define PP() pop()
#define BB() back()
#define FF() front()
#define cls() clear()
#define emp() empty()
#define len(x) x.length()
#define sz(x) ((int)x.size()) //컨테이너에서 사용
#define ms(a) memset(a, 0, sizeof(a)) //0으로 초기화
#define rep(i, n) for(int i = 0; i < n ; i++)
#define rrep(i, r, n) for(int i = r; i < n ; i++)
#define rrrep(i, r, n) for(ll i = r; i < n ; i++)
#define _rrep(i, r, n) for(int i = r; i >= n; i--)
#define _rrrep(i, r, n) for(ll i = r; i >= n; i--)
#define each(x, a) for (auto& x: a)
#define all(x) x.begin(),x.end() //STL에서 전체 처리할때 사용
#define range(x, r, n) x.begin() + r, x.begin() + n //STL에서 구간설정
#define ct continue
#define br break
#define rt return
#define _TYF typedef //코드줄이기
#define _UG using
#define _TCE template <class T> inline
//#define MAX 
const int IMAX = INT32_MAX; const int IMIN = INT32_MIN;
const long long LMAX = LLONG_MAX; const long long LMIN = LLONG_MIN;
const long double PI = 3.141592653589793238462643383279502884197;
_UG std::vector; _UG std::stack; _UG std::queue; _UG std::tuple; _UG std::set; _UG std::list; _UG std::bitset; _UG std::string; _UG std::pair; _UG std::greater;
_UG std::tie; _UG std::sort; _UG std::max_element; _UG std::min_element; _UG std::fill; _UG std::stoi; _UG std::stod; _UG std::stof; _UG std::stol; _UG std::stold; _UG std::stoll; _UG std::stoul; _UG std::stoull;
_UG std::map;
_TYF long long ll; _TYF unsigned long long ull;
_TYF pair<int, int> pii; _TYF pair<double, int> pdi; _TYF pair<int, double> pid; _TYF pair<double, double> pdd; _TYF pair<int, ll> pil;
_TYF pair<ll, int> pli; _TYF pair<ll, ll> pll; _TYF pair<ull, ull> pullull; _TYF pair<int, char> pic; _TYF pair<char, int> pci;
_TYF pair<char, char> pcc; _TYF pair<long, char> plc; _TYF pair<char, long> pcl; _TYF pair<ll, char> pllc; _TYF pair<char, ll> pcll;
_TYF pair<ull, char> pullc; _TYF pair<char, ull> pcull; _TYF pair<int, string> pis; _TYF pair<string, int> psi; _TYF pair<long, string> pls;
_TYF pair<string, long> psl; _TYF pair<ll, string> plls; _TYF pair<string, ll> psll; _TYF pair<ull, string> pulls;
_TYF pair<string, ull> psull; _TYF pair<string, string> pss;
_TYF tuple<int, int, int> tiii; _TYF tuple<int, int, int, int> tiiii;
_TYF tuple<ll, ll, ll> tlll; _TYF tuple<ll, ll, ll, ll> tllll;
_TYF vector<string> vs; _TYF queue<string> qs; _TYF stack<string> ss; _TYF dq<string> dqs; _TYF pq<string> pqs; _TYF dq<string> dqs;
_TYF vector<char> vc; _TYF queue<char> qc; _TYF stack<char> sc; _TYF dq<char> dqc; _TYF pq<char> pqc; _TYF dq<char> dqc;
_TYF vector<int> vi; _TYF queue<int> qi; _TYF stack<int> si; _TYF dq<int> dqi; _TYF pq<int> pqi; _TYF dq<int> dqi;
_TYF vector<pii> vii; _TYF queue<pii> qii; _TYF stack<pii> sii; _TYF dq<pii> dqii; _TYF pq<pii> pqii; _TYF dq<pii> dqii;
_TYF vector<tiii> viii; _TYF queue<tiii> qiii; _TYF stack<tiii> siii; _TYF dq<tiii> dqiii; _TYF pq<tiii> pqiii; _TYF dq<tiii> dqiii;
_TYF vector<tiiii> viiii; _TYF queue<tiiii> qiiii; _TYF stack<tiiii> siiii; _TYF dq<tiiii> dqiiii; _TYF pq<tiiii> pqiiii; _TYF dq<tiiii> dqiiii;
_TYF vector<pll> vll; _TYF queue<pll> qll; _TYF stack<ll> sll; _TYF dq<pll> dqll; _TYF pq<pll> pqll; _TYF dq<pll> dqll;
_TYF vector<tlll> vlll; _TYF queue<tlll> qlll; _TYF stack<tlll> slll; _TYF dq<tlll> dqlll; _TYF pq<tlll> pqlll; _TYF dq<tlll> dqlll;
_TYF vector<tllll> vllll; _TYF queue<tllll> qllll; _TYF stack<tllll> sllll; _TYF dq<tllll> dqllll; _TYF pq<tllll> pqllll; _TYF dq<tllll> dqllll;
_TCE T sq(T num) { rt num* num; }//제곱함수
_TCE T GCD(T num1, T num2) { if (num2 == 0) rt num1; rt GCD(num2, num1 % num2); }
_TCE T LCM(T num1, T num2) { if (num1 == 0 || num2 == 0) rt num1 + num2; rt num1* (num2 / GCD(num1, num2)); }
//STL 전용 초기화 함수들 ( ms~~ )
_TCE void msq(T& a) { while (!a.empty()) a.PP(); }//queue clear
_TCE void msv(T& a) { a.cls(); }//vector clear
_TCE void msdq(T& a) { a.cls(); }//deque clear
_TCE void msm(T& a) { a.cls(); }//map clear
_TCE void mss(T& a) { while (!a.empty()) a.PP(); }//stack, set clear
_TCE void mspq(T& a) { while (!a.empty()) a.PP(); }//priority_queue clear
//pii operator - (pii a, pii b) { rt pii(a.first - b.first, a.second - b.second); }
//bool operator <= (pii a, pii b) { rt a.first <= b.first && a.second <= b.second; } 
//bool operator >= (pii a, pii b) { rt a.first >= b.first && a.second >= b.second; } 
//bool operator < (pii a, pii b) { if (a == b) return false; rt a <= b; } 
//bool operator > (pii a, pii b) { if (a == b) return false; rt a >= b; }

void func();

struct Trie {
	map<string, Trie*> node; //key로 문자열, value로 포인터를가짐

	//비 재귀방법으로 트라이구조를 만듬
	void insert(vs &list) {
		Trie* cur = this;
		rep(i, sz(list)) {
			//키에 해당하는 value가 있는지 확인
			if (cur->node[list[i]] == nullptr) 
				//없으면 키에대한 value를 지정해줌
				//(새로운 객체를 생성해줌 => 포인터가 새로운 객체공간을 가리킴)
				cur->node[list[i]] = new Trie(); 
			cur = cur->node[list[i]];
		}
	}

	void DFS(int idx) {
		for (auto iter : node) {
			rep(_, idx) {
				pr("--");
			}
			pr("%s\n", iter.first.tc());
			iter.second->DFS(idx + 1);
		}
	}
};

//프로그램 메인 로직
void func() {
	int N;
	sc("%d", &N);

	Trie trie;
	rep(i, N) {
		int K;
		sc("%d", &K);
		char c[300];
		sc("%c%[^\n]s", &c[0], &c);
		vs list(K, "");
		int k = 0;
		rep(j, 300) {
			if (c[j] == ' ') {
				k++;
				ct;
			}
			if(c[j] == '\0') {
				br;
			}
			list[k] += c[j];
		}

		trie.insert(list);
		trie.DFS(0);
	}

}

int main(void) {
	func();

	rt 0;
}