[G2] 백준 21276번 계보 복원가 호석 C++ 위상 정렬, 해시맵, set

리뷰

 

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

이를 기반으로 몇 개의 가문이 존재했는 지, 각 가문에 대한 정보를 출력하는 문제

m값을 입력 받아놓고 for문을 n번 돌려서 틀렸다 ㅠ

 

전역 변수

• n, m : 이름의 개수 n, 부모 및 조상을 나타내는 간선의 개수 m
• sum : 시조의 개수를 저장할 변수
• dic : 시조간 인접 리스트를 구현하기 위한 해시맵
• cnt : 이름 간 선순위가 필요한 경우의 수를 저장할 해시맵
• result : 이름 간 직계 자손을 저장하기 위한 해시맵
• q : 선순위가 더 이상 없는 이름을 저장하기 위한 큐
• sizo : 시조의 이름을 오름차순으로 정렬하기 위한 셋

 

함수

1. input

 

void input()

 

이름을 입력 받고 해시맵, 인접 리스트를 초기화 하기 위한 함수

1. n을 입력 받고 n개의 이름을 입력 받아 해당 이름의 dic, cnt, result 해시맵을 초깃값으로 초기화 해준다.
2. m을 입력 받고 m개의 간선 정보를 입력 받아 dic 해시맵에 단방향 간선을 추가해 준다.
3. 단방향 간선을 추가할 때에는 역방향으로 삽입해 주어야 한다.

 

2. solution

void solution()

 

선순위를 기반으로 위상정렬을 진행하는 함수

1. 각 이름의 인접리스트를 순회하며 인접리스트에 존재하는 이름의 cnt를 증가시킨다.
2. 각 이름의 cnt개수를 체크하며 개수가 0인 경우 sum을 증가시키고 sizo, q에 이름을 추가시킨다.
3. q가 빌때까지 반복문을 진행하며 이름을 뽑아내 준다.
4. 해당 이름의 인접리스트를 순회하며 자식의 cnt개수를 감소시킨다.
5. 만약 자식의 cnt가 0이 되었다면 큐에 자식을 추가하고, 부모의 result해시맵에 자식을 추가해 준다.

 

3. output

void output()

 

 

시조의 개수, 시조 정보, 직계 정보를 출력해 주는 함수

1. 시조의 개수 sum을 출력해 준 후 줄바꿈 해준다.
2. 공백을 기준으로 sizo에 들어있는 요소를 출력해 준다.
3. result 해시맵을 순회하며 result의 key를 출력해 준다.
4. 공백을 기준으로 result의 value의 사이즈를 출력해 준다.
5. 공백을 기준으로 result의 value에 존재하는 자식의 이름을 출력해 준다.
6. 마지막에 줄바꿈을 실행해 준다.

 

 

문제풀이

1. input 함수를 통해 각 입력값을 받아주고, dic, result, cnt해시맵을 초기화 해준다.
2. solution함수를 통해 위상정렬을 진행하고 각 해시맵과 셋, 변수를 최신화 해준다.
3. output함수를 통해 문제에서 출력하고자 하는 값들을 출력해 준다.

 

참고 사항

• 시조와 이름 모두 오름차순으로 정렬해 주어야 하기에 map과 set를 사용해 준다.
• 인접 리스트를 초기화 할때 문자열 a, b를 입력 받았다면 b -> a로 간선을 추가해 주어야 한다.
• 이름의 개수는 n개이며 간선의 개수는 m개이다, 문제가 안풀린다면 오타를 주의하자

 

정답 코드

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

int n, m, sum;
map<string, vector<string>> dic;
map<string, int> cnt;
map<string, set<string>> result;
queue<string> q;
set<string> sizo;

void input() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s; cin >> s;
		dic[s] = {};
		cnt[s] = 0;
		result[s] = {};
	}

	cin >> m;
	for (int i = 0; i < m; i++) {
		string a, b; cin >> a >> b;
		dic[b].push_back(a);
	}
}

void solution() {
	for (const auto& d : dic) {
		for (const string& s : d.second) cnt[s]++;
	}

	for (const auto& c : cnt) {
		if (!c.second) {
			sum++;
			sizo.insert(c.first);
			q.push({ c.first });
		}
	}

	while (!q.empty()) {
		string cur = q.front(); q.pop();
		for (const string& s : dic[cur]) {
			if (!--cnt[s]) {
				q.push(s);
				result[cur].insert(s);
			}
		}
	}
}

void output() {
	cout << sum << "\n";
	for (const string& s : sizo) cout << s << " ";
	cout << "\n";

	for (const auto r : result) {
		cout << r.first;
		cout << " " << r.second.size();
		for (const string& s : r.second) cout << " " << s;
		cout << "\n";
	}
}

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

	input();
	solution();
	output();
}