[백준/C++] #5021 왕위 계승 (위상 정렬)

문제

 

이 문제는 가족 관계를 방향 그래프(DAG)로 나타내어, 각 개인이 왕의 혈통을 얼마나 이어받았는지 계산하는 문제이다.

부모가 두명으로 이루어져있다는 점에서 좀 난항을 겪었다가, 자식에 대한 부모 정보를 따로 저장하는 map을 만들어 문제를 해결했다. 

풀이

자식이 부모의 부모가 되는 경우가 없다는 조건이 명시 되어 있으므로 사이클이 없는 방향 그래프(DAG)임을 알 수 있다. 따라서 위상 정렬을 이용하여 부모의 혈통이 먼저 계산된 후 자식에게 전파되도록 구현할 수 있다.!!

혈통 계산 방식은 부모로부터 반씩 혈통을 받는 방식이다. 왕의 혈통을 1.0으로 설정한 후, 각 자식의 혈통을 부모들의 혈통의 절반씩 더한 값으로 계산하면 된다.

 

위상정렬은 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph)에서 노드들의 선후 관계를 유지하면서 정렬하는 알고리즘이다. 각 노드는 진입차수(들어오는 간선의 수)를 가지며, 진입 차수가 0인 노드부터 순서대로 제거하면서 정렬을 수행한다. 

위상 정렬의 동작 과정
1. 진입 차수가 0인 노드를 큐에 삽입한다.
2. 큐에서 노드를 꺼내면서 해당 노드와 연결된 간선을 제거한다.
3. 간선이 제거된 후 새롭게 진입 차수가 0이 된 노드를 큐에 삽입한다.
4. 모든 노드를 방문할 때까지 반복한다.

 

일단 이름으로 부모와 자식이 입력되니까, 보다 편한 연산을 위해 MAP으로 이름과 번호를 매핑해줬다. 그리고, MAP으로 진입차수와 혈통 비율을 저장하게끔 했고, 부모에 따른 자식을 찾을 수 있는 2차 배열과 각 자식의 부모 정보를 저장하는 MAP을 사용했다. 

 

전체 로직은 다음과 같다. 

1. 왕의 혈통은 1로 설정하면스 왕 이름과 숫자를 매핑해준다. 

2. 자식과 부모를 반복 입력받으며 숫자와 이름을 매핑한다. 부모 -> 자식 그래프를 생성하고, MAP으로 각 자식의 부모 정보도 저장해준다. 이때, 부모와 자식의 진입 차수 또한 초기화 혹은 증가 시켜준다. 

*자식의 경우 부모는 2명이기에 진입 차수를 2 증가시켜준다. 

 

3. 혈통 계산을 실행한다. 

3-1. 진입 차수가 0인 사람(노드)들을 큐에 추가시킨다. 
3-2. 큐에서 노드를 꺼내면서 해당 부모과 연결된 간선을 제거한다. = 진입 차수 1 감소
3-3. 자식의 진입 차수가 0인 경우에 혈통을 계산한다. 이때, 자식을 통해 부모(두명)를 알아낸다. 
3-4. 부모의 혈통 점수를 가지고 자식의 혈통 점수를 알아낸다. 
3-5. 진입 차수가 0인 자식은 큐에 삽입하여 후에 그의 자식들을 탐색할 준비를 한다. 

 

4. 입력받은 후보자 이름으로 ID를 찾고, 가장 높은 점수를 가진 후보자를 출력한다. 

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;

int n, m;
string king;
int number = 0;
unordered_map<string, int> num; // 이름과 번호 매핑
unordered_map<int, int> indegree; // 진입 차수
unordered_map<int, double> close; // 혈통 비율 저장
vector<vector<int>> graph; // 부모 → 자식 관계 그래프
unordered_map<int, pair<int, int>> parents; // 각 자식의 부모 정보 저장

queue<int> q;

void calculateBloodline() {
    cout << "\n[초기 진입 차수 상태]\n";
    for (auto& entry : indegree) {
        cout << "ID: " << entry.first << ", Indegree: " << entry.second << endl;
    }

    // 부모가 없는 사람(진입 차수 0)부터 시작
    for (auto& entry : indegree) {
        if (entry.second == 0) {
            cout << "큐에 추가: ID " << entry.first << endl;
            q.push(entry.first);
        }
    }

    // 혈통 계산 시작
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        cout << "처리 중: ID " << now << ", 현재 혈통: " << close[now] << endl;

        for (int child : graph[now]) {
            indegree[child]--; // 부모 1명 처리 완료

            // 부모의 모든 진입 차수가 0이 된 경우에만 혈통 계산
            if (indegree[child] == 0) {
                int parent1 = parents[child].first;
                int parent2 = parents[child].second;

                close[child] = 0;

                if (close.find(parent1) != close.end()) { // 없으면 짜피 0이기에
                    close[child] += close[parent1] / 2;
                }
                if (close.find(parent2) != close.end()) {
                    close[child] += close[parent2] / 2;
                }

                cout << " → 자식 ID " << child << " 혈통 업데이트: " << close[child] << endl;
                q.push(child);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    cin >> king;

    graph.resize(2 * n + 10);

    if (num.find(king) == num.end()) {
        num[king] = number++;
    }
    close[num[king]] = 1.0; // 왕의 혈통 1.0으로 설정

    cout << "\n[입력된 왕: " << king << "]" << endl;

    for (int i = 0; i < n; i++) {
        string child, par1, par2;
        cin >> child >> par1 >> par2;

        // ID 할당
        if (num.find(child) == num.end()) num[child] = number++;
        if (num.find(par1) == num.end()) num[par1] = number++;
        if (num.find(par2) == num.end()) num[par2] = number++;

        int childID = num[child];
        int parent1ID = num[par1];
        int parent2ID = num[par2];

        // 그래프 생성
        graph[parent1ID].push_back(childID);
        graph[parent2ID].push_back(childID);

        // 부모 정보 저장
        parents[childID] = { parent1ID, parent2ID }; 

        // 부모 진입 차수
        if (indegree.find(num[par1]) == indegree.end()) {
            indegree[num[par1]] = 0;
        }
        if (indegree.find(num[par2]) == indegree.end()) {
            indegree[num[par2]] = 0;
        }

        // 부모가 2명이므로 자식의 진입 차수 2 증가
        indegree[childID] += 2; 
    }

    // 디버깅: 입력된 그래프 확인
    cout << "\n[그래프 정보 (부모 → 자식 리스트)]\n";
    for (size_t i = 0; i < graph.size(); i++) {
        if (!graph[i].empty()) {
            cout << "ID " << i << " → Children: ";
            for (int child : graph[i]) {
                cout << child << " ";
            }
            cout << endl;
        }
    }

    // 혈통 계산 실행
    calculateBloodline();

    double closest_score = 0.0;
    string closest_name = "";

    cout << "\n[왕위 계승 후보 검사 시작]\n";
    //cout << "a" << num["besty"] << endl;
    for (int i = 0; i < m; i++) {
        string name;
        cin >> name;
        
        if (num.find(name) == num.end()) {
            continue;
        }

        int id = num[name];
        double score = close[id];

        cout << "후보: " << name << ", 혈통 점수: " << score << endl;

        if (score > closest_score) {
            closest_score = score;
            closest_name = name;
        }
    }

    cout << closest_name << endl;
    cout << close[num[closest_name]] << endl;
    return 0;
}