[백준 21276] 계보 복원가 호석 (C++)

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

문제

---

석호촌에는 N 명의 사람이 살고 있다. 굉장히 활발한 성격인 석호촌 사람들은 옆 집 상도 아버님, 뒷집 하은 할머님 , 강 건너 유리 어머님 등 모두가 한 가족처럼 살아가고 있다.

그러던 어느 날, 유구한 역사를 지닌 석호촌의 도서관에 화재가 나서 계보들이 모두 불타고 말았다. 그래도 계보는 있어야 하지 않겠느냐는 마을 어르신인 대일 촌장님의 의견에 따라 석호촌 사람들은 계보 복원가 호석에게 의뢰를 맡기기로 했다.

적어도 현재를 함께 살아가는 N 명의 계보는 복원하고 싶은 호석이는 조사를 통해서 각자가 기억하는 조상들의 이름들을 구해냈다. 다행히도 석호촌의 맑은 정기 덕분에 기억력이 굉장히 좋은 주민들은 모든 조상을 완벽하게 기억하고 있다. 또한, 각 가문은 한 명의 시조를 root로 하는 트리 형태를 띈다는 것도 알아냈다. 이 때 "조상"이란, "자신의 부모"와 "부모의 조상"을 모두 합친 것을 의미한다.

이를 기반으로 몇 개의 가문이 존재했는 지, 각 가문에 대한 정보를 출력하는 프로그램을 작성해서 호석이를 도와주자!

 

입력

---

첫번째 줄에 석호촌에 살고 있는 사람의 수 N 이 주어진다. 두번째 줄에는 현재 살고 있는 사람들의 이름이 차례대로 주어진다. 모든 이름은 길이 1 이상 6 이하의 알파벳 소문자로 이뤄지며, 중복된 이름은 존재하지 않는다.

세번째 줄에는 기억하는 정보의 개수 M 이 주어진다. 이어지는 M개의 줄에는 "X Y" 꼴로 기억들이 주어지는데, 이는 곧 X의 조상 중에 Y가 있다는 것을 의미하며 같은 정보가 중복되어 주어지지 않는다. 입력에 모순이 있는 경우는 주어지지 않는다.

 

출력

---

첫번째 줄에는 가문의 개수 K 를 출력하라. 두 번째 줄에는 각 가문의 시조들의 이름을 공백으로 구분하여 사전순으로 출력하라.

세번째 줄부터는 이름의 사전순 대로 사람의 이름과 자식의 수, 그리고 사전순으로 자식들의 이름을 공백으로 구분하여 출력하라.

 

제한

---

• 1 ≤ N ≤ 1,000
• 0 ≤ M ≤ N×(N-1)/2

문제 풀이

---

 위상 정렬 문제.

 

각 조상에 대해 후손을 저장한다. (아래 코드에는 childs) 후손과 조상을 M번 입력받아야 하므로 각 이름에 대한 인덱스를 저장하는 map(아래 코드 중 indexes)를 하나 생성하여 현재 살고 있는 사람을 입력받을 때 인덱스를 저장해둔다. 그리고 후손과 조상을 M번 입력받을 때 indexes에서 후손과 조상의 인덱스를 얻어와 각 조상에 대해 후손을 저장하는 자료구조 (childs)에 저장한다. 또한 후손은 indegree를 하나 가지게 되므로 1 증가시켜준다.

 

평범한 위상 정렬 문제처럼 indegree를 저장하는 자료구조를 탐색하여 indegree가 0인 사람들을 큐에 넣어준다. 이후 큐가 빌 때까지 현재 큐의 front에 위치한 사람을 가져와, 그 사람의 후손들을 탐색하여 indegree를 하나씩 감소시켜준다. indegree가 0이라면 이제 남은 사람들 중 조상이 없고 후손만 있다는 뜻이다. 따라서 큐 front에 위치한 사람 - 후손이 마지막 연결이므로 해당 후손이 큐 front에 위치한 사람의 자식이 된다. 큐에 넣고 자식 정보를 저장하는 map(아래 코드에는 m)에 해당 정보를 저장한다.

 

아래는 코드.

#include <iostream>
#include <map>
#include <set>
#include <utility>
#include <algorithm>
#include <queue>
using namespace std;

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

	int N, M;
	string name, X, Y;
	cin >> N;
	map<string, set<string>> m;
	map<string, int> indexes;
	map<string, set<string>>::iterator it;
	vector<string> family;
	pair<string, int>* inDegree = new pair<string, int>[N];
	vector<string>* childs = new vector<string>[N];
	queue<pair<string, int>> q;
	for (int i = 0; i < N; i++)
	{
		cin >> name;
		set<string> s;
		m.insert({ name, s });
		indexes.insert({ name, i });
		inDegree[i] = pair(name, 0);
	}
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> X >> Y;
		int xIndex = indexes[X];
		int yIndex = indexes[Y];
		childs[yIndex].push_back(X);
		inDegree[xIndex].second++;
	}
	for (int i = 0; i < N; i++)
	{
		if (inDegree[i].second == 0)
		{
			q.push(pair(inDegree[i].first, i));
			family.push_back(inDegree[i].first);
		}
	}
	while (!q.empty())
	{
		pair<string, int> current = q.front();
		int index = current.second;
		for (int i = 0; i < childs[index].size(); i++)
		{
			string  child = childs[index].at(i);
			int childIndex = indexes[child];
			inDegree[childIndex].second--;
			if (inDegree[childIndex].second == 0)
			{
				q.push(pair(child, childIndex));
				m[current.first].insert(child);
			}
		}
		q.pop();
	}
	sort(family.begin(), family.end());
	cout << family.size() << "\n";
	for (int i = 0; i < family.size(); i++)
	{
		if (i != family.size()-1)
		{
			cout << family.at(i) << " ";
		}
		else
		{
			cout << family.at(i)<<"\n";
		}
	}
	for (it = m.begin(); it != m.end(); it++)
	{
		cout << it->first << " "<<it->second.size();
		for (set<string>::iterator iter = it->second.begin(); iter != it->second.end(); iter++)
		{
			cout << " " << *iter;
		}
		cout << "\n";
	}
	return 0;
}