[2020 Goricon] BOJ 20119 클레어와 물약

문제 링크 : www.acmicpc.net/problem/20119

20119번: 클레어와 물약

문제에서 주어진 레시피는, 한 물약을 만들기 위해 필요한 물약에 대한 정보이다.

즉, 레시피의 왼쪽에 있는 물약들을 모두 가지고 있어야 오른쪽의 물약을 만들 수 있다.

이는 곧 하나의 물약을 만들기 위해서는 다른 물약의 제조가 선행되어야 함을 의미하며, 따라서 이 문제를 위상 정렬 문제로 접근할 수 있다.

위상 정렬 (Topological Sort)

 

하지만 일반적인 위상 정렬로는 이 문제를 올바르게 해결할 수 없다.

위 그림과 같이 레시피가 주어졌을 때, 위상 정렬을 위해 그래프로 나타낸 각 물약 간의 관계는 위 그림의 오른쪽과 같을 것이다.

1번 물약에 해당하는 정점에 대해, 정점의 진입 차수는 총 5이지만 실제로는 3개의 물약(2, 3, 4) 또는 2개의 물약(5, 6)으로도 1번 물약을 제조할 수 있다.

또한, 각 레시피는 독립적이기 때문에, 어느 한 레시피에 필요한 모든 물약을 가지고 있지 않다면 몇 개의 물약을 가지고 있어도 해당 물약은 만들 수 없다.

이는 곧 하나의 레시피의 재료 물약들만 모두 가지고 있다면 반드시 그 물약을 만들 수 있다는 것과 같다.

 

따라서 이 문제의 각 정점을 다음과 같은 구조체 형태로 선언하여 위상 정렬의 결과를 출력한다.

 - 해당 물약을 만드는 레시피들의 모음

 - 레시피들 각각에 대한 재료의 갯수 (이는 곧 진입 차수와 같다)

 - 해당 물약을 만들 수 있는지에 대한 여부

레시피들 간 겹치는 물약이 존재할 수 있기 때문에, 하나의 재료 물약을 만들 수 있다면 모든 레시피에 대해 해당 물약이 충족되었음을 체크해야 한다.

 

※ 주어진 레시피들을 토대로 그래프를 구성하면 사이클이 존재하는 경우가 많다. 하지만 문제 내에서 최초에 보유하고 있는 물약들의 목록이 제시되므로, 그냥 그 정점을 큐에 넣고 위상 정렬을 시작하면 된다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
typedef pair<int, int> p;
 
typedef struct {
    int number;
    bool possible = false;
    vector<vector<int>> indegree;
    vector<int> ind_cnt;
    vector<int> adj;
}element;
 
int n, m;
element ele[200001];
vector<int> have;
 
void bfs() {
    queue<element> que;
    for (int i = 0; i < have.size(); i++) que.push(ele[have[i]]);
 
    while (!que.empty()) {
        element cur = que.front();
        que.pop();
 
        int num = cur.number;
 
        for (int i = 0; i < cur.adj.size(); i++) {
            //이미 만든 물약이라면 가지 않음
            int nextnode = cur.adj[i];
            if (ele[nextnode].possible) continue;
 
            //아직 만들지 않았다면 nextnode의 레시피를 검색
            //cur에 해당하는 재료에 대해 확인 표시
            for (int j = 0; j < ele[nextnode].indegree.size(); j++) {
                if (ele[nextnode].possible) break;
                for (int k = 0; k < ele[nextnode].indegree[j].size(); k++) {
                    //nextnode의 j번째 레시피에 대해, k번째 재료가 cur에 해당하는지 확인
                    if (num == ele[nextnode].indegree[j][k]) {
                        ele[nextnode].indegree[j][k] = -1;
                        ele[nextnode].ind_cnt[j]--;
                        if (ele[nextnode].ind_cnt[j] == 0) {
                            ele[nextnode].possible = true;
                            break;
                        }
                    }
                }
            }
 
            if (ele[nextnode].possible) {
                have.push_back(nextnode);
                que.push(ele[nextnode]);
            }
        }
    }
}
 
void init() {
    int k, x, r, L, y;
    vector<int> ingredients;
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++) ele[i].number = i;
 
    for (int i = 0; i < m; i++) {
        ingredients.clear();
        cin >> k;
        for (int j = 0; j < k; j++) {
            cin >> x;
            ingredients.push_back(x);
        }
        cin >> r;
        //그래프로 이어줌
        for (int j = 0; j < ingredients.size(); j++) {
            ele[ingredients[j]].adj.push_back(r);
        }
        ele[r].indegree.push_back(ingredients);
        ele[r].ind_cnt.push_back(ingredients.size());
    }
    //보유 중인 물약
    cin >> L;
    for (int i = 0; i < L; i++) {
        cin >> y;
        ele[y].possible = true;
        have.push_back(y);
    }
 
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    bfs();
 
    printf("%d\n", have.size());
    sort(have.begin(), have.end());
    for (int i = 0; i < have.size(); i++) printf("%d ", have[i]);
    printf("\n");
 
 
    return 0;
}