[ 백준 BOJ ] 21276번 - 계보 복원가 호석 (C++)

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

생각 흐름

• 처음에는 노드에 대한 구조체를 만들고 계속 이어주면 된다고 생각했다. 하지만 입력이 주어질 때 바로 위에 부모가 주어지기도 하지만 그 위에 조상도 주어지므로 노드로 이어주는 방식은 안 되겠다 생각했다.
• 어떻게 하지 생각하다가 결국 트리 형태이므로, 각 노드마다 부모를 저장하고, 각 부모의 부모 노드의 개수를 세주는 방식을 사용하면 가장 많은 부모 노드를 가진 부모 노드가 해당 노드의 바로 위의 부모 노드라고 생각했다.
• 예를 들어, haeun의 경우 부모 노드를 minji, doha를 가지고 있다. 이 때 minji의 부모 노드의 개수는 0이고, doha의 부모 노드의 개수는 1이므로 haeun의 바로 위 부모 노드는 doha가 된다.
• 이렇게 부모 노드를 찾으면 해당 노드를 부모 노드의 자식 노드에 넣어준다.

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int N;
vector<string> names;
int M;
map<string, vector<string>> children;
map<string, vector<string>> parents;
vector<string> parentCount[1001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>N;
    for(int i = 0; i<N; i++){
        string tmp;
        cin>>tmp;
        
        names.push_back(tmp);
        parents[tmp] = {};
        children[tmp] = {};
    }
    cin>>M;
    for(int i = 0; i<M; i++){
        string a, b;
        cin>>a>>b;
        
        parents[a].push_back(b);
    }
    
    for(auto i : parents){
        parentCount[i.second.size()].push_back(i.first);
    }
    
    int i = 1;
    while(true){
        if(parentCount[i].empty()) break;
        
        for(auto j : parentCount[i]){
            int maxNum=-1;
            string parent;
            for(auto k : parents[j]){
                if(maxNum<(int)parents[k].size()){
                    maxNum = (int)parents[k].size();
                    parent = k;
                }
            }
            children[parent].push_back(j);
        }
        
        i++;
    }
    
    cout<<parentCount[0].size()<<endl;
    sort(parentCount[0].begin(), parentCount[0].end());
    for(auto a : parentCount[0]) cout<<a<<" ";
    cout<<endl;
    
    for(auto a : children){
        cout<<a.first<<" ";
        cout<<a.second.size()<<" ";
        sort(a.second.begin(), a.second.end());
        for(auto b : a.second){
            cout<<b<<" ";
        }
        cout<<endl;
    }
    
    return 0;
}