[백준/BOJ] 백준 14725번 : 개미굴

www.acmicpc.net/problem/14725

14725번: 개미굴

트리를 만들어서 문제를 해결했다.

 

코드

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

int n;

struct node {
	string food;
	vector<node*> children;
};

bool cmp(node* a, node* b)
{
	return ((a->food) < (b->food));
}

void Insert(node* parent, vector<string> info, int index)
{
	if (index >= info.size()) //정보를 다 넣었을때
		return;

	string this_food = info[index];

	bool check = false;
	for (int i = 0; i < parent->children.size(); i++)
	{
		//this_food의 정보가 있을때
		if ((parent->children[i])->food == this_food)
		{
			check = true;
			Insert(parent->children[i], info, index + 1);
			break;
		}
	}

	if (check == false) //this_food의 정보가 없을때
	{
		node* new_node = new node();
		new_node->food = this_food;

		(parent->children).push_back(new_node);

		Insert(parent->children[parent->children.size() - 1], info, index + 1);
	}
}

void Solve(node* parent, int cnt)
{
	if (cnt != 0)
	{
		for (int i = 0; i < cnt - 1; i++)
		{
			cout << "--";
		}

		cout << parent->food << "\n";
	}

	if (parent->children.size() == 0)
		return;

	//사전 순서가 앞서는 순서로 정렬
	sort(parent->children.begin(), parent->children.end(), cmp);

	for (int i = 0; i < parent->children.size(); i++)
		Solve(parent->children[i], cnt + 1);
}

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

	cin >> n;

	node* root = new node();
	root->food = " ";

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

		cin >> k;
		for (int j = 0; j < k; j++)
		{
			string input;
			cin >> input;

			info.push_back(input);
		}
		Insert(root, info, 0);
	}

	Solve(root, 0);

	return 0;
}