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

이 문제는 주민들이 자신의 조상을 완벽히 기억하고 있을 때, 계보를 복원하는 문제이다.

이때, 입력은 주민들의 이름과 주민 $X$의 조상 $Y$가 이름의 형태로 주어지므로 그래프 관계로 표현해야한다. 그리고 이를 바탕으로 트리를 만들어야한다. 즉, 주민들의 관계를 정렬해주어야 하기 때문에, 방향 그래프로 표현해야한다.

어차피 위상 정렬을 해야하므로, 진입 차수 indeg를 트리를 구성하면서 미리 구해두는 것이 편리하다.

이제, 문제를 본격적으로 해결해보자.

먼저, 주민 수와 주민의 이름이 주어진다. 이때, 우리는 출력시 정렬해서 출력해야 하므로 입력을 받은 뒤 곧바로 정렬해 두어도 상관이 없다. 그리고, 그래프를 표현할 때는 정점을 정수로 구분하는 것이 편리하므로, 이름이 주어졌을 때 어떤 정점인지 곧바로 알아낼 수 있도록 해싱하도록 하자. unordered_map<string, int> id를 이용하면 될 것이다.

그 다음에는 총 간선 갯수와 간선이 주어진다. 이 때, 진입 차수 indeg를 세어주면 나중에 위상 정렬하기 편리해 진다. 그래프의 간선 정보는 인접 리스트 vector<int> adj[1001]에 저장하도록 하자. 이 때, 주의할 점은 입력이 $X$, $Y$순으로 주어지고 $X$의 조상이 $Y$라는 것이다. 하지만, 우리는 트리를 구성해야 하므로, 노드 $I$의 자식 노드가 무엇인지가 궁금하다. 따라서, adj에는 $Y$에서 $X$ 방향의 간선을 저장해야한다.

이제, 위상 정렬을 해볼 차례이다. 가장 먼저 방문 가능한 정점은 진입 차수가 $0$인 정점이다. 따라서 $1$ ~ $N$까지 루프를 돌면서 트리의 루트들을 vector<int> anc에 저장해보자. anc에 저장된 노드들은 서로 다른 독립된 트리들의 루트가 된다.
즉, 분리 집합의 시작점을 구한 것이므로 이는 서로 다른 가문의 시조와 대응된다. 문제에서 요구한 가문의 갯수 $K$와 가문의 시조들을 구한 것이므로 이를 출력하고 다음 로직을 진행해보자.

다음으로, 각 노드의 자식을 구해 트리를 완성해야 한다. 이 문제에서 유의깊게 살펴보아야 하는 것은 노드는 자신의 조상을 모두 기억하고 있다는 것이다. 따라서, 부모-자식 관계이기 위해서는 진입 차수 indeg가 오직 1만 차이 나야한다.
이 성질을 이용한다면 트리의 자식을 손쉽게 알 수 있다. 다시 말해, 노드 $I$의 자식 ch[i]는 adj[i]에 속한 정점들 중에 진입 차수가 1 차이나는 것들이라는 것을 알 수 있다. 이때, 출력시에 정렬된 상태를 유지할 수 있도록 adj[i]를 정렬해주도록 하자.

이제, 트리를 완전히 구성했고 이름도 사전순으로 정렬된 상태이므로, 차례로 이름, 자식 수, 자식들을 출력해 나가면 된다.

#include <bits/stdc++.h>
using namespace std;

int n, m;
string name[1001], s1, s2;
unordered_map<string, int> id;
vector<int> adj[1001], anc, ch[1001];
int indeg[1001];

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

	cin >> n;
	for (int i = 1; i <= n; i++) cin >> name[i];
	sort(name + 1, name + n + 1);
	for (int i = 1; i <= n; i++) id[name[i]] = i;

	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> s1 >> s2;
		adj[id[s2]].push_back(id[s1]);
		indeg[id[s1]]++;
	}

	for (int i = 1; i <= n; i++) {
		if (!indeg[i]) anc.push_back(i);
	}

	cout << anc.size() << "\n";
	for (int i : anc) cout << name[i] << " ";
	cout << "\n";

	for (int i = 1; i <= n; i++) {
		sort(adj[i].begin(), adj[i].end());
		for (int c : adj[i]) {
			if (indeg[c] - indeg[i] == 1) ch[i].push_back(c);
		}
	}

	for (int i = 1; i <= n; i++) {
		cout << name[i] << " " << ch[i].size() << " ";
		for (int c : ch[i]) cout << name[c] << " ";
		cout << "\n";
	}
}