0. 문제
1. 풀이
문제만 읽어보면 간단히 위상 정렬로 해결할 수 있을 것 같은데, 예시 입출력을 확인하면 그렇지 않다.
위상 정렬은 DAG, 사이클이 없는 방향그래프에만 적용할 수 있는데 이 문제는 각 물약(정점)들이 서로를 선행 노드로 가리키는 경우가 발생한다.
이는 정점 단위로 그래프를 구성해야 한다는 생각을 가지기 때문인데, 문제에서는 물약을 만들 수 있는 레시피 가 주어지므로 임의의 정점의 선행 정점들은 다른 정점이 아닌 레시피이다.
또, 정점을 탐색하며 갱신해 나가는 방식에서, 만들어지지 않은 물약들을 기준으로 탐색하게 되면 결국 다시 재귀적으로 시작 지점으로 돌아와 가면서 탐색해야 한다는 단점이 있으므로 만들어진 물약들을 기준으로 탐색해야 하는데 이 경우 만들어진 물약을 가지고 만들 수 있는 물약의 정보도 각 정점이 포함해야 한다.
따라서 각 정점은 다음과 같은 정보를 포함해야 한다.
- 물약 번호(이 정보는 배열의 인덱스로 대체 가능)
- 물약의 레시피(들. 임의의 물약 $r$을 만드는 레시피가 반드시 1개인 것은 아니다.)
- 해당 물약이 재료가 되는 물약들
- 해당 물약을 가지고 있는지 여부
struct Potion
{
//int num 이 정보는 배열 인덱스로 대체
std::vector<std::vector<int>> recipes; // 이 물약을 만들기 위한 레시피 리스트
std::vector<int> next; // 이 물약을 재료로 삼는 물약들의 리스트
bool belong = false;
}따라서 문제의 예시 입출력에 주어진 조건 일부를 각각 도식화하면 다음과 같다.
…
3 1 5 7 2
…
2 3 4 5
2 4 5 3
2 5 6 4
결국, 각 물약들의 레시피와 가지고 있는 물약이 주어지면, 가지고 있는 물약들을 기준으로 만들 수 있는 물약들(next)을 탐색하며 각 물약들이 가진 레시피들(recipes) 중 하나라도 모든 구성 물약을 가지고 있는 레시피가 있다면 belong을 true로 변경하고 가지고 있는 물약 리스트에 해당 물약을 추가한다.
이 과정을 모든 가지고 있는 물약에 반복하면 정답을 찾을 수 있게 된다.
2. 코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
constexpr int MAXN = 200001;
struct Potion
{
bool belong = false; // 가지고 있는지(만들 수 있는지) 여부
vector<vector<int>> recipes; // 레시피들
vector<int> next; // 만들 수 있는 물약들
};
// 물약 배열. 1부터 200000(최대) 까지 인덱스가 물약 번호와 동일함.
vector<Potion> recipe(MAXN);
void bfs(int n)
{
queue<int> q;
for (int i = 1; i <= n; i++)
{
if (recipe[i].belong) // 가지고 있는 물약들을 큐에 enqueue
{
q.push(i);
}
}
while (!q.empty())
{
auto cur = recipe[q.front()];
q.pop();
for (int i = 0; i < cur.next.size(); i++)
{
auto next = cur.next[i];
if (recipe[next].belong) // 현재 물약이 이미 갖고 있는 물약이라면 더 진행할 필요 없으므로 넘어감
{
continue;
}
// 현재 물약을 만들 수 있는 레시피들을 탐색하며 만들 수 있는지 여부 파악
for (int j = 0; j < recipe[next].recipes.size(); j++)
{
auto curRecipe = recipe[next].recipes[j];
bool canMade = true;
// 레시피에 속한 모든 물약들을 가지고 있다면 canMade가 true, 하나라도 없다면 false가 저장됨
for (int k = 0; k < curRecipe.size(); k++)
{
if (!recipe[curRecipe[k]].belong)
{
canMade = false;
break;
}
}
// 만들 수 있는 물약이라면 belong을 true로 만들고 큐에 enqueue
if (canMade)
{
recipe[next].belong = true;
q.push(next);
break;
}
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("input.txt", "r", stdin);
int n, m;
cin >> n >> m;
int cnt;
vector<int> ingredient;
for (int i = 0; i < m; i++)
{
cin >> cnt; // 레시피를 구성하는 재료 개수 입력받기
ingredient.clear();
for (int j = 0; j < cnt; j++)
{
int p;
cin >> p;
ingredient.push_back(p);
}
int r;
cin >> r;
for (int j = 0; j < cnt; j++)
{
// 각 재료를 구성하는 물약들에 해당 물약으로 만들 수 있는 목록을 갱신(r의 재료들에 r을 만들 수 있는 물약으로 지정)
recipe[ingredient[j]].next.push_back(r);
}
// 물약 r을 만들 수 있는 레시피 갱신
recipe[r].recipes.push_back(ingredient);
}
cin >> cnt;
for (int i = 0; i < cnt; i++)
{
int index;
cin >> index;
recipe[index].belong = true; // 현재 가지고 있는 물약들 목록 갱신
}
bfs(n);
cnt = 0;
for (int i = 1; i <= n; i++)
{
if (recipe[i].belong)
{
cnt++;
}
}
cout << cnt << "\n";
for (int i = 1; i <= n; i++)
{
if (recipe[i].belong)
{
cout << i << " ";
}
}
return 0;
}3. 결과
