백준 5021 왕위계승

5021번: 왕위 계승

문제

유토피아의 왕이 사망했다. 왕은 자손을 남기지 않고 사망했기 때문에, 왕위를 계승할 사람을 지목하지 않았다. 왕실 귀족은 왕위를 주장하기 시작했다. 유토피아의 법에는 왕의 계승자가 없는 경우에, 나라를 세운 사람과 혈통이 가까운 사람이 유토피아를 통치한다는 조항이 있다.

나라를 세운 사람과 혈통이 가장 가까운 사람은 그의 자손이 아닌 사람과 피가 덜 섞인 사람이다. 모든 사람은 아버지의 혈통과 어머니의 혈통을 반 씩 받게 된다. 나라를 세운 사람의 자식은 1/2 왕족이며, 그 아들이 왕족이 아닌 사람과 결혼한 경우에는 아들의 자식은 1/4 왕족이 된다.

가장 나라를 세운 사람과 혈통이 가까운 사람을 찾는 프로그램을 작성하시오. 

 

풀이

DFS 공부하기 좋은 문제이다.

예제를 그래프로 그려보자면 아래와 같다.

여기서 유토피아를 세운 사람은 edwardi 이므로 edwardi의 피를 1로 잡고 후손들의 피가 어떻게 될지 계산해 보았다.

이문제를 DFS로 풀려면 그래프를 뒤집어서 생각하면 편하다.

입력이 주어질때마다 자기자신의 부모 두명을 저장하고, dfs로 부모를 계속 호출했다가 더이상 호출할 부모가 없으면 자기 자신의 피를 리턴한다. 

map 컨테이너를 사용해 가족 정보와 피 정보를 저장해주었다.

#include <iostream>
#include <string>
#include <map>
#include <vector>
 
using namespace std;
 
map<string, vector<string>> family;    // 가족 정보
map<string, double> d;    // 피 정보
 
double dfs(string name) 
{
    if (family[name].empty()) {    // 더이상 부모가 없으면
        return d[name];    // 해당 이름의 피를 리턴
    }
    string parent1 = family[name][0];
    string parent2 = family[name][1];
    double ret = (dfs(parent1) + dfs(parent2)) / 2;
    d[name] = ret;
    return ret;
}
 
void init(string king)
{
    for (auto element : d) {
        element.second = 0;
    }
    d[king] = 1;
}
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, M;
    cin >> N >> M;
    string king;
    cin >> king;
    
    for (int i = 0; i < N; ++i) {
        string child;
        string parent1, parent2;
        cin >> child >> parent1 >> parent2;
        family[child].push_back(parent1);    
        family[child].push_back(parent2);
        d[child] = d[parent1] = d[parent2] = 0;
    }
    double ans = 0;
    string next = "";
    for (int i = 0; i < M; ++i) {
        string candidate;
        cin >> candidate;
        init(king);
        double temp = dfs(candidate);
        if (ans < temp) {
            ans = temp;
            next = candidate;
        }
    }
    cout << next << "\n";
    return 0;
}