백준 21276 계보복원가호석 c++ // 위상정렬, 조상찾기주의점, 문자열을 idx로 바꿔서 풀어라

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

 

1. 문자열을 idx로 바꿔서 풀어라

1. map<string, int> m을 두고 sort 후

m["철수"] = 0 , m["석열"]=1 ... 이런식으로 할당하면 된다.

2. 이래야 실수를 줄이고 디버깅, 복잡도등 이점이 많다..

 

2. 조상찾기주의점

석호 철수(조상) 일때,

석호 <- 철수 로 두어야함!

그래야 철수의 indegree가 0이됨.

* 위상정렬의 기본 idea가 indegree가 0인점을 제거해 나간다는 점을 꼭 생각할것!!

 

3. 의사코드

1. 문자열을 idx로 바꿈

2. 입력만 문자열일뿐 숫자 위상정렬과 같이 생각하면 쉽다.

자료구조가 숫자 그자체에서 해당 idx로 바뀌었을 뿐이다.

vector<int> adj[1001]; //i노드의 인접리스트들의 idx
vector<int> child[1001]; //i노드의 진짜자식들 의 idx

3. 0인정점 == 조상 이고

4. nxt 차수가 0이 되는것 == 직계자식이다!

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n,m;
map<string, int> idx; //문자를 숫자로 ,상덕=1, 철수=2 ...
vector<string> v;
vector<int> adj[1001]; //i노드의 인접리스트들의 idx
vector<int> child[1001]; //i노드의 진짜자식들 의 idx
int indeg[1001]; //i노드의 인디그리

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        v.push_back(s); //사람명단
    }
    //문자를 숫자로 ,idx[상덕]=1, idx[철수]=2 ...
    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 s1, s2; // 상덕 <- 철수(조상)
        cin >> s1 >> s2;
        int u = idx[s1], v = idx[s2];
        adj[v].push_back(u);
        indeg[u]++;
    }
    queue<int> q;
    vector<int> ancestor; //최초조상 특 == 인디그리가 0임
    for (int i = 0; i < n; ++i) {
        if (indeg[i] == 0) {
            ancestor.push_back(i);
            q.push(i);
        }
    }

    while (q.size()) {
        auto cur = q.front(); q.pop();
        for (auto nxt : adj[cur]) {
            indeg[nxt]--;
            if (indeg[nxt] == 0) {
                q.push(nxt);
                child[cur].push_back(nxt);
            }
        }
    }
    cout << ancestor.size() << "\n";
    for (auto i : ancestor) {
        cout << v[i] << " ";
    }
    cout << "\n";
    for (int i = 0; i < n; ++i) {
        cout << v[i] << " " << child[i].size() << " ";
        sort(child[i].begin(), child[i].end());
        for(auto j : child[i]) {
            cout << v[j] << " ";
        }
        cout << "\n";
    }


    return 0;

}