백준 21276번 계보 복원가 호석

문제 요약

$N, M$이 주어지는데 사람이 N명이고 조상관계가 M개 주어진다는 뜻이다.

어떤 사람 $A$가 $B$의 조상이란 뜻은, $B$가 $A$의 부모이거나, $A$의 부모의 조상이란 뜻이다.

가문이란 한 명의 시조를 root로 하는 트리의 형태를 띈다. 가문의 수와, 각 가문의 시조와, 각 사람의 자식들을 출력해야 한다. 이 때, 모든 사람들을 본인의 조상을 완벽하게 기억하고 있고 이 내용이 주어진다.

$ N \le 1000, 0 \le M \le N(N-1)/2$

풀이

본인의 조상을 완벽하게 기억하고 있다는 조건이 좀 중요하다. 가문이 트리 구조를 가진다고 제시했으니 이 조건은 바꿔 말하면 어떤 노드가 트리에 속해 있을 때, 해당 트리 내에서 본인의 모든 조상을 알려준다는 것이다.

이를 토대로 풀이를 생각해보자. 일단 주어지는 조상 관계를 전부 방향이 있는 간선으로 나타내고, 각 사람을 정점으로 나타내자. 입력으로 X Y가 들어오면 Y에서 X로 가는 간선을 추가하자.

그러면 indegree가 0인 노드들은 전부 어떤 가문의 시조임을 알 수 있다. 시조는 본인의 가문에 속하는 모든 정점들로 나가는 간선이 있을 것이다. 이 간선들을 지워보자.

그러면, 시조의 자식들은 또 indegree가 0이 될 것이다. 그리고 이 자식들을 지우면 시조의 자식들의 자식들의 indegree가 0이 될 것이다.

이러한 과정을 가지는 알고리즘이 떠오르지 않는가? 위상정렬이다.

위상정렬을 진행하면서 간선을 지워나가는데 어떤 간선 $(u, v)$를 지웠을 때 $v$의 indegree가 0이 된다면 $v$는 $u$의 자식이 된다. 따라서, 이 정보를 추가해 나가면 문제에서 원하는 것을 얻을 수 있다.

한 가지, 정점의 이름이 숫자가 아니라 문자열로 주어지는데 일단 모든 사람 이름을 입력 받은뒤에 정렬하고 차례대로 번호를 0번부터 붙여나가면 사전순으로 출력하기가 편하다. 번호를 붙이는 데에는 map을 쓰면 좋다.

#include<bits/stdc++.h>
using namespace std;
map<string, int> idx;
vector<vector<int>> G(1005);
vector<string> v;
vector<vector<int>> children(1005);
int N, M;
int indegree[1005];
int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N;
    for(int i=0;i<N;++i) {
        string s; cin >> s;
        v.push_back(s);
    }
    sort(v.begin(), v.end());
    for(int i=0;i<N;++i) idx[v[i]] = i;
    cin >> M;
    for(int i=0;i<M;++i) {
        string a, b;
        cin >> a >> b;
        int u = idx[a];
        int v = idx[b];
        G[v].push_back(u);
        indegree[u]++;
    }
    queue<int> q;
    vector<int> super_father;
    for(int i=0;i<N;++i) {
        if(indegree[i] == 0) {
            super_father.push_back(i);
            q.push(i);
        }
    }
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        for(int nxt : G[cur]) {
            indegree[nxt]--;
            if(indegree[nxt] == 0) {
                children[cur].push_back(nxt);
                q.push(nxt);
            }
        }
    }
    cout << super_father.size() << '\n';
    for(int i : super_father) cout << v[i] << ' ';
    cout << '\n';
    for(int i=0;i<N;++i) {
        cout << v[i] << ' ' << children[i].size() << ' ';
        sort(children[i].begin(), children[i].end());
        for(int j : children[i]) cout << v[j] << ' ';
        cout << '\n';
    }
    return 0;
}