[백준 5021] 왕위 계승

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

 

1. 문제 이해

왕이 사망했는제 자손을 남기지 않고, 계승할 사람 지목하지 않음.

유토피아의 법에는 왕의 계승자가 없는 경우에, 나라를 세운 사람과 혈통이 가까운 사람이 유토피아를 통치한다는 조항이 있음

 

첫째 줄에 N과 M

둘째 줄에 유토피아를 세운 사람의 이름

N개 줄에는 가족 정보가 주어짐 ( => 가족 정보 : 자식의 이름 / 부모 이름 / 부모 이름)

M개 줄에 왕위 계승 받기 주장하는 사람 주어짐

 

2. 조건

나라를 세운 사람과 혈통이 가장 가까운 사람은 그의 자손이 아닌 사람과 피가 덜 섞인 사람이다.

모든 사람은 아버지의 혈통과 어머니의 혈통을 반 씩 받게 된다.

나라를 세운 사람의 자식은 1/2 왕족이며, 그 아들이 왕족이 아닌 사람과 결혼한 경우에는 아들의 자식은 1/4 왕족이 된다

 

3. 풀이

가중치가 주어진 유향 그래프이므로 위상정렬로 풀 수 있다고 판단했다.

이해 하기 쉽게 그림을 그려봤다.

빨강 > 주황 > 노랑 > ... > 보라색 으로 갈수록 혈통과 멀어지는 것이다.

자식은 부모꺼 더하기 / 2이다 !

위에 적용해보면 보라색은 1/16, 파란색은 1/8이 나온다. 따라서 파란색을 return 하게 된다.

코드를 짜보자

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

int n, m;
double maxBlood = -1;
string builder, child, parent1, parent2, result;
map<string, vector<string>> family; // parent, 자식
map<string, pair<int, double>> in_degree; //자신, parent, 피
vector<string> wants;

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

    cin >> n >> m;
    cin >> builder;
    in_degree[builder] = {0, 1};

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

        //기존에 이미 parent 있다면 추가 x, 없다면 추가
        if (in_degree.find(parent1) == in_degree.end()) {
            in_degree[parent1] = {0, 0};
        }
        if (in_degree.find(parent2) == in_degree.end()) {
            in_degree[parent2] = {0, 0};
        }
        in_degree[child] = {2, 0}; //부모, 일단 피 0

        family[parent1].push_back(child);
        family[parent2].push_back(child);
    }

    for (int i = 0; i < m; i++) {
        cin >> child;
        wants.push_back(child);
    }

    queue<string> q;
    for (const auto &name: in_degree) {
        if (name.second.first == 0) { //parent 0이면 (=in_degree 0)
            q.push(name.first);
        }
    }

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

        for (const string &kid: family[parent]) { //자식들 보기
            in_degree[kid].second += in_degree[parent].second; //부모꺼 더하기
            --in_degree[kid].first;
            if (in_degree[kid].first == 0) {
                q.push(kid);
                in_degree[kid].second /= 2; //자식은 1/2
            }
        }
    }

    for (const string& want: wants) { //원하는 사람 중 제일 큰 second(피) 찾기
        if (maxBlood < in_degree[want].second) {
            maxBlood = in_degree[want].second;
            result = want;
        }
    }
    cout << result;

    return 0;
}