[baekjoon 21276] 계보 복원가 호석 (트리, 위상정렬, 맵) (C++)

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

21276번: 계보 복원가 호석

가문의 족보를 복원해야 하는 문제이다. 각 가문은 tree구조이고, 각 주민의 조상이 주어지는데 조상은 자신의 부모 또는 부모의 부모가 포함되어 있다.

 

따라서 이 문제를 풀기 위해서 필요한 것은, 순서 관계에 의해 주어진 입력값을 위상 정렬하는 것과 문자열로 주어진 입력값을 맵을 이용 해서 인덱싱 해주는 것이 필요하다.

 

전체적인 풀이 과정은

1. 입력값을 map을 이용해서 문자열, 숫자 꼴로 저장해준다.

2. 위상 정렬을 위해서 벡터에 저장 및 inDegree를 세준다.

3. 그렇게 되면 조상은 inDegree가 0인 것을 찾으면 된다. (조상으로 들어오는 화살표는 없다)

4. 조상들을 이용해서 각 족보에서 위상 정렬을 해준다.

5. 위상 정렬을 진행하면서 나와 연결된 노드 중, 나와의 연결을 끊으면 inDegree가 0이 된다는 것은 즉, 내 직계 자식이라는 소리이므로 트리 구조로 저장해준다.

6. 5의 과정이 끝난 후 모든 인덱스를 순회하면서 문자열로 변환해주며 벡터에 저장해서 이름 순 정렬, 내 자식들 또한 이름 순 정렬을 해준다.

+ 출력 시 가문과 상관없이 처음에 입력받은 이름들을 오름차순 출력을 해야 한다.

 

여러 개념이 섞인 재밌는 문제였던 것 같다.

코드에 주석을 달아놨으니 보면 이해가 될 것이다.

 

#include <iostream>
#include <unordered_map>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct name { // 정렬하기 위해 저장하기 위한 구조체
	string parent;
	vector<string> sonList;

	name(string _parent) {
		parent = _parent;
	}
};

bool compare(name n1, name n2) {
	return n1.parent < n2.parent;
}

int n, e, inDegree[1001]; // 위상정렬 용 진입차수
string s,x,y;
unordered_map<string, int> m; // 이름에 인덱스를 매핑
unordered_map<int, string> mInt; // 인덱스를 이용해서 이름을 찾기 위함
vector<int> v[1001]; // 간선 입력용
vector<string> ancestorList; // 조상리스트
vector<int> answerTree[1001]; // 족보 트리 제작용
vector<name> nameList; // 정답출력용 벡터

void topologicalSort(int startX) {
	queue<int> q;
	q.push(startX);

	while (!q.empty()) {
		int x = q.front();
		q.pop();

		for (int i = 0; i < v[x].size(); i++) {
			int nx = v[x][i];
			inDegree[nx]--;
			if (inDegree[nx] == 0) {
				answerTree[x].push_back(nx); // 나와 직접 연결된 자식이므로 삽입
				q.push(nx);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s;
		m[s] = i; // 문자열 -> 인덱스 매핑
		mInt[i] = s; // 인덱스 -> 문자열 매핑
	}
	cin >> e;

	for (int i = 0; i < e; i++) {
		cin >> x >> y; // x 조상 중 y가 있다.
		int son = m[x];
		int ancestor = m[y];
		v[ancestor].push_back(son);
		inDegree[son]++; // 위상정렬을 위해 진입차수 계산
	}

	for (int i = 0; i < n; i++) {
		if (inDegree[i] == 0) { // 처음에 진입차수가 0이면 최고조상이다.
			ancestorList.push_back(mInt[i]);
		}
	}

	sort(ancestorList.begin(), ancestorList.end());

	cout << ancestorList.size() << "\n"; // 정답 사이즈 출력

	for (auto k : ancestorList) {
		cout << k << " ";
		int start = m[k];
		topologicalSort(start); // 조상을 시작으로 족보 탐색을 한다.
	}
	cout << "\n";

	for (int i = 0; i < n; i++) { // 가문 상관없이 nameList에 넣어주기 위함, 인덱스 0~n-1 
		string p = mInt[i]; // 인덱스에 해당하는 이름
		name n1(p); // 구조체 생성
		for (int j = 0; j < answerTree[i].size(); j++) { // 아까 생성한 트리를 돌며 자식들을 문자열로 변환해주고
			string son = mInt[answerTree[i][j]];
			n1.sonList.push_back(son); // 구조체 자식 리스트에 넣어준다.
		}
		sort(n1.sonList.begin(), n1.sonList.end()); // 자식 또한 정렬해주고
		nameList.push_back(n1); // 구조체리스트에 넣어준다.
	}

	sort(nameList.begin(), nameList.end(), compare); // 구조체 역시 이름 순으로 정렬해준다.

	for (int i = 0; i < nameList.size(); i++) {
		name temp = nameList[i]; // 이름 및 자식들 출력
		cout << temp.parent << " " << temp.sonList.size() << " ";
		for (int j = 0; j < temp.sonList.size(); j++) {
			cout << temp.sonList[j] << " ";
		}
		cout << "\n";
	}
}