취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 3018번 문제인 캠프파이어이다.
문제는 아래 링크를 확인하자.

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

set 자료구조를 이용해 문제를 해결해보자.

i번 사람이 현재 알고 있는 노래를 모두 담고 있는 집합을 st[i]라 하자. 이 때, 1번을 제외한 사람들이 모였을 때에는 각 사람들이 알고 있는 노래의 집합의 합집합을 구해 각 모인 사람의 st[i]를 그 집합으로 바꿔주고, 1번을 포함한 사람들이 모였을 때에는 각 모인 사람의 아는 노래에 새 노래를 하나씩 집어넣는 것으로 문제를 해결할 수 있다. 이 과정에서 1번이 k번째로 만드는 새 노래의 이름을 k로 지으면 구현을 편리하게 할 수 있다.

아래는 제출한 소스코드이다.

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

int N, E;
set<int> st[101];
int num;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> E;
	while (E--) {
		int K; cin >> K;
		vector<int> vec;
		set<int> tmp;
		bool is_bard = 0;
		while (K--) {
			int x; cin >> x;
			vec.emplace_back(x);
			if (x < 2) is_bard = 1;
		}
		if (is_bard) {
			num++;
			for (auto& x : vec) st[x].insert(num);
		}
		else {
			for (auto& x : vec) {
				for (auto& xx : st[x]) tmp.insert(xx);
			}

			for (auto& x : vec) {
				for (auto& xx : tmp) st[x].insert(xx);
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		if (st[i].size() == num) cout << i << '\n';
	}
}