[백준/C++] 5021번 왕위계승

백준

---

🤔문제 이해

나라를 세운 사람이 1 왕족이고, 왕족이 아닌 외부 사람은 0왕족이다.

부모의 왕족 점수를 각각 2로 나누어 더한 값이 자식의 왕족 점수가 되고, 왕위를 계승받기를 주장하는 사람들 중 왕족 점수가 가장 높은 사람을 출력하면 되는 문제이다.

---

💡첫번째 아이디어

예제 입력

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을 바탕으로 짠 가계도이다. helen과 wilhelm의 자식 matthew의 관계가 입력에서 먼저 나오지만 결과적으로 helen 또한 왕족이 되므로 입력 중간에 계산은 불가능해 보였다.

 

그래서 일단 자식 이름을 key로 하고 부모 이름과 왕족 점수를 value로 갖는 map 자료구조를 사용해

자식-부모 관계를 저장해놓고 현재 자식에 대해 그 부모에 대해 다음과 같이 나누어 생각해보았다.

1. 부모 한쪽만 왕족

  1-1. 그 왕족의 왕족 점수가 존재하는 경우(0이 아닌 경우)

  1-2. 그 왕족의 왕족 점수가 존재하지 않는 경우 (0인 경우)

2. 부모 양쪽 다 왕족

  2-1. 그 왕족의 왕족 점수가 둘다 존재하는 경우

  2-2. 그 왕족의 왕족 점수가 왼쪽 부모만 존재하는 경우

  2-3. 그 왕족의 왕족 점수가 오른쪽 부모만 존재하는 경우

  2-4. 그 왕족의 왕족 점수가 둘다 존재하지 않는 경우

 

부모-자식 관계를 알려주는 입력값들은 따로 배열에 저장해놓고 첫 입력은 나라를 세운 왕과 그의 배우자, 그의 자식 관계이므로 가장 처음 입력값부터 자식의 왕족 점수를 찾아줬다.

while문 안에서 모든 입력값만큼 for문을 돌면서 그 부모가 왕족인데 왕족 점수가 존재하지 않는다면 그냥 pass해주고, 존재한다면 점수를 채워주었다. 

정해줘야 하는 자식만큼 계산을 해주었다면 while문을 빠져나오게 했다. 

 

마지막 m만큼 입력받은 귀족의 왕족 점수를 map에서 찾아 비교해가면서 최댓값을 갖는 귀족의 이름을 출력해주면 끝!

 

❌첫번째 제출

시간초과가 났다. 솔직히 처음부터 재귀함수를 쓰면 될 것 같다고 생각했는데 n과 m의 최대가 50이길래 굳이 쓰지 않아도 될 줄 알았는데...

---

💡두번째 아이디어

만약 부모가 하나 또는 둘이 왕족일 때 그 부모의 왕족 점수가 없는 경우엔 sovle함수를 재귀호출하여 그 부모를 자식 취급하여 왕족 점수를 찾아주는 방식으로 풀었다. 

 

🔥풀이🔥

자식의 왕족 점수가 0일 때 아래의 경우에 따라 왕족 점수를 다르게 구한다.

1. 부모 한쪽만 왕족

  1-1. 그 왕족의 왕족 점수가 존재하는 경우(0이 아닌 경우)

  1-2. 그 왕족의 왕족 점수가 존재하지 않는 경우 (0인 경우)

2. 부모 양쪽 다 왕족

  2-1. 그 왕족의 왕족 점수가 둘다 존재하는 경우

  2-2. 그 왕족의 왕족 점수가 왼쪽 부모만 존재하는 경우

  2-3. 그 왕족의 왕족 점수가 오른쪽 부모만 존재하는 경우

  2-4. 그 왕족의 왕족 점수가 둘다 존재하지 않는 경우

 

 

1-1과 2-1의 경우엔

부모의 왕족 점수를 각각 /2해서 더해준다.

1-2, 2-2, 2-3, 2-4의 경우엔

부모의 왕족 점수를 찾기 위해 부모를 자식취급하여 왕족점수를 찾는 함수를 재귀호출해주고, 

재귀호출로 인해 정해진 부모의 왕족 점수로 자식의 왕족 점수를 계산해준다.

자식의 왕족 점수가 정해지면 return

 

마지막으로 왕위 계승을 주장하는 귀족들의 왕족 점수를 비교해 가장 큰 왕족 점수를 가진 귀족의 이름을 출력한다.

---

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

using namespace std;

int n, m;
string first_king;
string input[51][3];

map<string, pair<pair<string, string>, double>> family;

void solve(string child, string par_left, string par_right) {
    if (family[child].second == 0) {
        if (family.count(par_left) && family.count(par_right)) {
            double left_num = family[par_left].second;
            double right_num = family[par_right].second;
            if (left_num != 0 && right_num != 0) {
                family[child] = {{par_left, par_right}, left_num / 2 + right_num / 2};
            } else if (left_num != 0 && right_num == 0) {
                solve(par_left, family[par_left].first.first, family[par_left].first.second);
                right_num = family[par_left].second;
                family[child] = {{par_left, par_right}, left_num / 2 + right_num / 2};
            } else if (left_num == 0 && right_num != 0) {
                solve(par_right, family[par_right].first.first, family[par_right].first.second);
                left_num = family[par_right].second;
                family[child] = {{par_left, par_right}, left_num / 2 + right_num / 2};
            } else {
                solve(par_left, family[par_left].first.first, family[par_left].first.second);
                right_num = family[par_left].second;
                solve(par_right, family[par_right].first.first, family[par_right].first.second);
                left_num = family[par_right].second;
                family[child] = {{par_left, par_right}, left_num / 2 + right_num / 2};
            }
        } else if (family.count(par_left) && !family.count(par_right)) {
            double left_num = family[par_left].second;
            if (left_num != 0) {
                family[child] = {{par_left, par_right}, left_num / 2};
            } else {
                solve(par_left, family[par_left].first.first, family[par_left].first.second);
                left_num = family[par_left].second;
                family[child] = {{par_left, par_right}, left_num / 2};
            }
        } else if (!family.count(par_left) && family.count(par_right)) {
            double right_num = family[par_right].second;
            if (right_num != 0) {
                family[child] = {{par_left, par_right}, right_num / 2};
            } else {
                solve(par_right, family[par_right].first.first, family[par_right].first.second);
                right_num = family[par_left].second;
                family[child] = {{par_left, par_right}, right_num / 2};
            }
        }
        return;
    }
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n >> m;
    cin >> first_king;

    family.insert({first_king, {{"", ""}, 1}});
    string a, b, c;
    for (int i = 0; i < n; i++) {
        cin >> a >> b >> c;
        family.insert({a, {{b, c}, 0}});
        input[i][0] = a;
        input[i][1] = b;
        input[i][2] = c;
    }
    for (int i = 0; i < n; i++) {
        string child = input[i][0];
        string par_left = input[i][1];
        string par_right = input[i][2];

        if (family[child].second == 0) {
            solve(child, par_left, par_right);
        }
    }


    string s;
    double large = 0;
    string large_man = "";
    for (int i = 0; i < m; i++) {
        cin >> s;
        if (large < family[s].second) {
            large_man = s;
            large = family[s].second;
        }
    }
    cout << large_man;


}