[백준/BOJ] 백준 20119번 : 클레어와 물약

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

20119번: 클레어와 물약

위상 정렬을 사용해서 문제를 해결했다. 만들어지는 물약이 처음 발견된 것일 때만 만들어지는 물약을 큐에 넣는 것에 주의하였다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
using namespace std;

int n, m;
vector<int> adj[200005]; //[물약번호] -> 레시피 번호
vector<int> recipe_indegree(200005, 0); //[레시피 번호]
vector<int> recipe_make(200005, 0); //[레시피 번호] = 만드는 물약
set<int> result;
set<int>::iterator it;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 1; i <= m; i++)
	{
		int k, r;

		cin >> k;
		for (int j = 0; j < k; j++)
		{
			int x;
			cin >> x;

			adj[x].push_back(i);
			recipe_indegree[i]++;
		}

		cin >> r;
		recipe_make[i] = r;
	}

	queue<int> q;
	int l;

	cin >> l;
	for (int i = 0; i < l; i++)
	{
		int y;
		cin >> y;

		if (result.count(y) == 0)
		{
			q.push(y);
			result.insert(y);
		}
	}

	while (!q.empty())
	{
		int here = q.front();
		q.pop();

		for (int i = 0; i < adj[here].size(); i++)
		{
			int this_recipe = adj[here][i];

			recipe_indegree[this_recipe]--;

			if (recipe_indegree[this_recipe] == 0) //해당 레시피의 물약을 모두 모았을때
			{
				if (result.count(recipe_make[this_recipe]) == 0) //만들어지는 물약이 처음 발견된 것일때
				{
					result.insert(recipe_make[this_recipe]);
					q.push(recipe_make[this_recipe]); //만들어지는 물약을 큐에 넣는다
				}
			}
		}
	}

	cout << result.size() << "\n";

	for (it = result.begin(); it != result.end(); it++)
	{
		cout << (*it) << " ";
	}

	return 0;
}