BOJ 5021

문제

왕위 계승 성공다국어

한국어   

1 초

128 MB

1005

340

255

34.884%

문제

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

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

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

입력

첫째 줄에 N과 M이 주어진다. (2 ≤ N, M ≤ 50)

둘째 줄에 유토피아를 세운 사람의 이름이 주어진다.

다음 N개 줄에는 가족 정보가 주어진다. 정보는 이름 세 개로 이루어져 있고, 공백으로 구분되어져 있다. 첫 번째 이름은 자식의 이름이고, 뒤의 두 이름은 부모의 이름이다.

다음 M개 줄에는 왕위를 계승받기를 주장하는 사람의 이름이 한 줄에 하나씩 주어진다.

모든 이름은 1~10글자이며, 알파벳 소문자로만 이루어져 있다. 나라를 세운 사람이 왕위를 계승하는 경우나, 누군가의 자식인 경우는 없다. 

출력

첫째 줄에 유토피아를 세운 사람과 가장 혈통이 가까운 사람의 이름을 출력한다. 항상 답이 유일한 경우만 입력으로 주어진다.

문제에 주어지는 가족 관계는 성별, 나이를 고려하지 않고 만들었기 때문에, 실제로는 말이 안되는 경우가 나올 수도 있다. 하지만, 모든 자식의 부모는 유일하며, 다시 자식이 부모의 부모가 되는 경우도 없다. 또, 한 사람이 여러 명의 자식이 될 수 도 없다.

예제 입력 1 복사

9 2
edwardi
charlesi edwardi diana
philip charlesi mistress
wilhelm mary philip
matthew wilhelm helen
edwardii charlesi laura
alice laura charlesi
helen alice bernard
henrii edwardii roxane
charlesii elizabeth henrii
charlesii
matthew

예제 출력 1 복사

matthew

예제 입력 2 복사

4 5
andrew
betsy andrew flora
carol andrew betsy
dora andrew carol
elena andrew dora
carol
dora
elena
flora
gloria

예제 출력 2 복사

elena​

풀이

풀이 자체는 간단하다. 

문제에서 명시되어 있지는 않지만 부모 둘을 아버지, 어머니로 두고

(아버지의 혈통값 + 어머니의 혈통값) * 1/2 를 한 값이 자녀의 혈통의 값이 된다.

이를 모든 자녀에 대해 계산해주면 되는 문제이다.

 

자녀와 부모에 대한 정보가 한번에 입력되므로 구조체로 선언해준다.

struct p{
    string name, parent1, parent2;
};

그리고 각각의 노드(자녀, 부모 각각의 이름) 의 혈통을 초기화해주기 위해 key-value table을 생성해준다.

부모와 자녀의 이름이 중복될 수 있기 때문에, 중복일 경우에 insert를 제한하는 map stl을 사용하였다.

 

map<string,double>m;

 

설립자의 혈통은 1로 초기화 해주고, 나머지는 다 0으로 초기화 해준다.

cin>>founder;
    m.insert({founder, 1});
    for(int i=0; i<N; i++){
        p new_p;
        cin>>new_p.name>>new_p.parent1>>new_p.parent2;
        v.push_back(new_p);
        m.insert({new_p.name, 0});
        m.insert({new_p.parent1, 0});
        m.insert({new_p.parent2, 0});
    }

혈통이 0이 아닌 경우는 무조건 설립자와 혈연관계가 있어야 하므로 queue를 하나 만들어 설립자를 넣어주고,

부모가 설립자인 경우부터 탐색해 나가도록 했다.

두명의 부모 중 하나라도 설립자이면 혈연관계를 계산하는 방식으로 이어지는 것이다.

다만 설립자의 자녀가 설립자의 배우자가 되듯이 설립자와 혈연관계가 있는 사람이 설립자와 혈연관계가 있는 사람의 배우자가 될 수 있으므로 설립자의 자녀, 설립자의 자녀의 자녀 ~~~ 를 queue에 계속 넣어주면서 계산이 바뀌는 경우도 모두 탐색해 주도록 했따.

queue<string>q;
    q.push(founder);
    while(!q.empty()){
        string cur = q.front();
        q.pop();
        for(auto node : v){
            if(node.parent1 == cur || node.parent2 == cur){
                string p1 = node.parent1, p2 = node.parent2;
                double p1_rate = m.find(p1)->second, p2_rate = m.find(p2)->second;
                m.find(node.name)->second = (p1_rate+p2_rate)/2;
                q.push(node.name);
            }
        }
    }

이러면 모든 사람의 혈연관계가 구해지게 되고, 문제가 풀린다.

 

다른 풀이

다 풀고 다른 풀이를 찾아보았을때

후보자를 입력하는 경우에 DFS로 탐색하는 것이 더 코드가 명료하다는 것을 알게 되었다.

 

부모의 혈연관계를 부모의 부모가 없을때까지 계산해 자녀를 계산하면 된다.

double dfs(string s){
    for(auto node : v){
        if(node.name == s){
            string p1 = node.parent1, p2 = node.parent2;
            double rate = (dfs(p1)+dfs(p2))/2;
            m[s] = rate;
            return rate;
        }
    }
    return m[s];
}

이 코드에서는 구조체 벡터 v의 원소의 name이 없으면 부모가 없는 것이기 때문에, 그때 map의 원소를 반환하도록 했다.

 

전체 코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <map>
using namespace std;
struct p{
    string name, parent1, parent2;
};
map<string,double>m;
vector<p>v;
int N, M;
double ans;
string founder, ans_s;
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>N>>M;
    cin>>founder;
    m.insert({founder, 1});
    for(int i=0; i<N; i++){
        p new_p;
        cin>>new_p.name>>new_p.parent1>>new_p.parent2;
        v.push_back(new_p);
        m.insert({new_p.name, 0});
        m.insert({new_p.parent1, 0});
        m.insert({new_p.parent2, 0});
    }
    queue<string>q;
    q.push(founder);
    while(!q.empty()){
        string cur = q.front();
        q.pop();
        for(auto node : v){
            if(node.parent1 == cur || node.parent2 == cur){
                string p1 = node.parent1, p2 = node.parent2;
                double p1_rate = m.find(p1)->second, p2_rate = m.find(p2)->second;
                m.find(node.name)->second = (p1_rate+p2_rate)/2;
                q.push(node.name);
            }
        }
    }
    for(int i=0; i<M; i++){
        string s1;
        cin>>s1;
        for(auto iter = m.begin(); iter != m.end(); iter++){
            if(iter->first == s1){
                if(iter->second > ans){
                    ans = iter->second;
                    ans_s = iter->first;
                }
            }
        }
    }
    cout<<ans_s;
    
}

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <map>
using namespace std;
struct p{
    string name, parent1, parent2;
};
map<string,double>m;
vector<p>v;
int N, M;
double ans;
string founder, ans_s;
double dfs(string s){
    for(auto node : v){
        if(node.name == s){
            string p1 = node.parent1, p2 = node.parent2;
            double rate = (dfs(p1)+dfs(p2))/2;
            m[s] = rate;
            return rate;
        }
    }
    return m[s];
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>N>>M;
    cin>>founder;
    m.insert({founder, 1});
    for(int i=0; i<N; i++){
        p new_p;
        cin>>new_p.name>>new_p.parent1>>new_p.parent2;
        v.push_back(new_p);
        m.insert({new_p.name, 0});
        m.insert({new_p.parent1, 0});
        m.insert({new_p.parent2, 0});
    }
    for(int i=0; i<M; i++){
        string s1;
        cin>>s1;
        double r=dfs(s1);
        if(r > ans){
            ans_s = s1;
            ans = r;
        }
    }
    cout<<ans_s;
    
}

 

포인트

혈연관계와 관련된 모든 변수는 double로 생성해주어야 한다.

ans변수를 int로 생성해서 두번 틀렸다.

 

map stl의 find함수가 key를 찾지 못했을 경우, map.end()를 반환한다는 것을 상기하자.

map.end()는 마지막 원소를 참조하는 것이 아닌 반복자의 마지막을 가리키는 것이다.