BOJ5021/ C++

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

5021번: 왕위 계승

백준 온라인저지 5021번 문제입니다. 

위상정렬을 이용해서 풀었습니다.

 

위상정렬 코드

#include<iostream>
#include<map>
#include<vector>
#include<string>
#include<queue>


using namespace std;


int n, m;
map<string, vector<string>> adj;
map<string, pair<int,double>> lineage;
string kingName;
vector<string>wantKing;

void init(string name) {
	if (lineage.find(name) == lineage.end())
		lineage[name] = { 0 ,0 };
}

void Input() {
	cin >> n >> m;
	cin >> kingName;

	while (n--) {
		string parnt1, parnt2;
		string name;

		cin >> name >> parnt1 >> parnt2;
		init(name);
		init(parnt1);
		init(parnt2);
		adj[parnt1].push_back(name);
		adj[parnt2].push_back(name);
		lineage[name] = { 2,0 };
	}
	while (m--) {
		string name;
		cin >> name;
		wantKing.push_back(name);
	}
	lineage[kingName] = { 0,1 };
}

void solution() {
	queue<string>q;
	string nextking;
	double bloodBalance = 0;

	for (auto iter : lineage) {
		if (iter.second.first == 0)
			q.push(iter.first);
	}

	while (!q.empty()) {
		string current = q.front();
		q.pop();

		for (auto iter : adj[current]) {
			string next = iter;
			lineage[next].second += lineage[current].second;
			if (--lineage[next].first == 0) {
				q.push(next);
				lineage[next].second /= 2;
			}
		}
	}
	for (auto iter : wantKing) {
		if (bloodBalance < lineage[iter].second) {
			bloodBalance = lineage[iter].second;
			nextking = iter;
		}
	}
	cout << nextking;
}

int main(void) {
	Input();
	solution();
}

 

 

dfs

#include<iostream>
#include<map>
#include<vector>
#include<string>


using namespace std;


int n, m;
map<string, vector<string>> adj;
map<string, double> lineage;
string kingName;
vector<string>wantKing;

void init(string name) {
	if (lineage.find(name) == lineage.end())
		lineage[name] = 0;
}

void Input() {
	cin >> n >> m;
	cin >> kingName;

	while (n--) {
		string parnt1, parnt2;
		string name;

		cin >> name >> parnt1 >> parnt2;
		init(name);
		init(parnt1);
		init(parnt2);
		adj[name].push_back(parnt1);
		adj[name].push_back(parnt2);
	}
	while (m--) {
		string name;
		cin >> name;
		wantKing.push_back(name);
	}
	lineage[kingName] = 1;
}

double dfs(string name) {
	if (lineage[name] != 0)
		return lineage[name];

	if (adj[name].empty())
		return lineage[name];

	return lineage[name] = (dfs(adj[name][0]) + dfs(adj[name][1])) / 2;
}

void solution() {
	string nextking;
	double bloodBalance = 0;
	for (auto iter : wantKing) {
		if (bloodBalance < dfs(iter)) {
			bloodBalance = dfs(iter);
			nextking = iter;
		}
	}
	cout << nextking;
}

int main(void) {
	Input();
	solution();
}

 

 

아이디어

유토피아를 세운 사람과 혈통이 가까운 사람을 찾기 위해서는 전입차수를 나타내는 변수에 혈통까지 같이 넣어서 계산을 하면되는 문제이다. 위상정렬으로도 풀고 dfs로도 풀어봤는데 두 방식의 차이는 위상정렬은 탑다운 방식으로 dfs는 바텀탑 방식이다 크게 주의할 부분은 없었던 것 같음