[ boj : 21276 ] 계보 복원가 호석

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

21276번: 계보 복원가 호석

문제 : 하나의 그래프가 주어지는데 이 그래프는 트리입니다. 이때 [자식,조상]의 관계가 주어질때 주어진 조건에 맞게 출력하시오

해설 : 좀 뇌절이 오는 문제였습니다 ㅠㅠㅠ 일단 중요한건 그래프를 그릴수만 있다면 뭐 dfs를 사용하던지, 위상정렬을 사용하던지 아니면 map에 담아서 출력하던지 등등 다양한 방법을 선택해 쉽게 답을 도출할 수 있지만 , 전 그래프를 만드는 부분이 좀 까다로웠는데 그 이유는 [자식,부모]의 관계가 주어지는 것이 아닌 모든 [자식,조상]의 관계가 주어졌기 때문에 필요없는 간선을 지워버리는 작업을 어떻게 해줘야 될지 해맸습니다.

간선을 지워버리는 작업은 트리의 depth를 이용하면 됩니다. 임의의 정점 x를 선택하였을때 이 정점의 depth가 y라면 이는 root 노드까지의 조상노드의 개수가 y라는 뜻입니다. 그러니 [자식,부모]의 관계를 표현하고 싶을땐 현재 부모라고 저장되어있는 노드들을 하나씩 비교해가며 y-1의 depth를 가지고 있다면 직속 부모라는 뜻이고 나머지 정보들을 싹다 필요없는 간선이 되버리는 것이죠.

이렇게 그래프를 만들어 준 후 위에서 말한 다양한 방법으로 답을 도출하면 됩니다. 전 map을 사용해서 해결하였습니다.

#include<bits/stdc++.h>

using namespace std;

int n, m;
vector<string> name;
map<string, int> mp;
map<string, vector<string>> p_info;
vector<string> adj[1000];

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

	cin >> n;
	name.resize(n);
	for (int i = 0; i < n; i++)
		cin >> name[i];	
	sort(name.begin(), name.end());
	for(int i=0;i<n;i++)
		mp[name[i]] = i;
	cin >> m;
	string x, y;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		p_info[x].push_back(y);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < p_info[name[i]].size(); j++) {
			string p_name = p_info[name[i]][j];
			int p_num = p_info[p_name].size();
			if (p_info[name[i]].size() - 1 == p_num) 
				adj[mp[p_name]].push_back(name[i]);
			
		}
	}
	vector<string> anc;
	for (int i = 0; i < n; i++) {
		if(p_info[name[i]].size()==0)
			anc.push_back(name[i]);
	}
	cout << anc.size() << "\n";
	for (string u : anc)
		cout << u << " ";
	cout << "\n";
	for (int i = 0; i < n; i++) {
		cout << name[i] << " "<<adj[i].size()<<" ";
		for (string u : adj[i])
			cout << u << " ";
		cout << "\n";
	}
	return 0;
}