[백준/BOJ] 백준 5021번 : 왕위 계승

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

5021번: 왕위 계승

각 부모에서 자식으로 가는 방향의 간선을 연결해 그래프를 만들고, 위상 정렬을 통해 각 정점의 점수(왕족의 비율)를 매겨 문제를 해결했다.

 

코드

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

int n, m;
int id_cnt = 0;
map<string, int> name_id;
vector<int> adj[200];
vector<int> indegree(200, 0);
vector<double> score(200, 0.0);

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

	cin >> n >> m;

	string king;
	cin >> king;

	id_cnt++;
	name_id.insert(make_pair(king, id_cnt));
	score[id_cnt] = 1.0;

	for (int i = 0; i < n; i++)
	{
		string child, parent1, parent2;
		cin >> child >> parent1 >> parent2;

		if (name_id.count(child) == 0)
		{
			id_cnt++;
			name_id.insert(make_pair(child, id_cnt));
		}

		if (name_id.count(parent1) == 0)
		{
			id_cnt++;
			name_id.insert(make_pair(parent1, id_cnt));
		}

		if (name_id.count(parent2) == 0)
		{
			id_cnt++;
			name_id.insert(make_pair(parent2, id_cnt));
		}

		int child_id = name_id[child];
		int parent1_id = name_id[parent1];
		int parent2_id = name_id[parent2];

		adj[parent1_id].push_back(child_id);
		indegree[child_id]++;
		adj[parent2_id].push_back(child_id);
		indegree[child_id]++;
	}

	queue<pair<int, double>> q; //(id, 점수)
	for (int i = 1; i <= id_cnt; i++) {
		if (indegree[i] == 0)
		{
			q.push(make_pair(i, score[i]));
		}
	}

	while (!q.empty()) {
		int here_id = q.front().first;
		double here_score = q.front().second;
		q.pop();

		for (int i = 0; i < adj[here_id].size(); i++) {
			int there_id = adj[here_id][i];

			indegree[there_id]--;
			score[there_id] += (here_score / 2);

			if (indegree[there_id] == 0)
				q.push(make_pair(there_id, score[there_id]));
		}
	}

	double max_score = -1.0;
	string max_name = "";

	for (int i = 0; i < m; i++)
	{
		string name;
		cin >> name;

		if (score[name_id[name]] > max_score)
		{
			max_score = score[name_id[name]];
			max_name = name;
		}
	}

	cout << max_name;

	return 0;
}