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

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

21276번: 계보 복원가 호석

위상정렬과 정렬을 이용한 문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

 1. n을 입력받습니다.

인접리스트를 만들어주기 위해서는 index를 int형으로 접근하도록 자료를 정리할 필요가 있습니다. map으로 이를 해결합니다. 나온 이름에 대해 자동으로 key값을 기준 오름차순 정렬을 해주기 때문에 편리합니다. [이름, 이름을 치환한 숫자], 반대로 두 개의 map을 선언합니다.

 

 2. m(연결정보)을 입력받습니다.

문자열 a, b를 입력받습니다. a는 자손 b는 조상의 의미로 a의 진입차수를 증가시켜주며 b -> a로 단방향 인접리스트를 구성합니다.

 

📔 풀이과정

 자신의 직계부모임을 알기 위해서는 위상정렬을 이용해야 합니다. 위상정렬을 위한 진입차수 개념은 이 같은 특징을 지닙니다.

 

 * 자신의 진입차수를 제거했을 때 연결되어 있는 정점의 진입차수가 0이 된다면 이는 직계자손라는 것을 알 수 있습니다. * 또한 각 가문의 시조는 진입차수가 없습니다.

 

1. 진입차수가 0인 것들은 직계부모임으로 vector string ancestor에 push해줍니다. 그 후 조상들의 이름을 사전순으로 정렬해줍니다.

 

2. 모든 조상들의 출발노드로하여 위상정렬을 실시합니다. 인접한 정점에 대해 진입차수를 1씩감소시키며 0이 된 순간 바로 x의 자손은 next라는 개념으로 또 다른 자손 인접리스트 childName에 push해줍니다.

 

3. childName의 원소들을 사전순으로 정렬하며 적절히 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int n, m, ind[1001], familyNum;
vector <int> graph[1001], childName[1001];
map <string,int> familyIdxMap;
map <int,string> familyNameMap;
vector <string> ancestor;

void topologySort(string anc){
    queue <int> q;
    q.push(familyIdxMap[anc]);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(auto next : graph[x]){
            ind[next]--;
            if(ind[next]) continue;
            childName[x].push_back(next);
            q.push(next);
        }
    }
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        familyIdxMap[s] = i;
        familyNameMap[i] = s;
    }
    
    cin >> m;
    for(int i = 0; i < m; i++){
        string a,b;
        cin >> a >> b;
        ind[familyIdxMap[a]]++;
        graph[familyIdxMap[b]].push_back(familyIdxMap[a]);
    }
    
    for(int i = 0; i < n; i++)
        if(!ind[i]) 
            ancestor.push_back(familyNameMap[i]);

    sort(ancestor.begin(),ancestor.end());

    for(auto a : ancestor) topologySort(a);

    cout << ancestor.size() << '\n';
    for(auto a : ancestor) cout << a << ' ';
    cout << '\n';

    for(auto f : familyIdxMap){
        cout << f.first << ' ' << childName[f.second].size() << ' ';
        vector <string> v;
        for(auto next : childName[f.second]) v.push_back(familyNameMap[next]);
        sort(v.begin(),v.end());
        for(auto el : v) cout << el << ' ';
        cout << '\n';
    }
}