[백준온라인] 9335번 소셜 광고

백준 9335번 - 소셜 광고 📢

🔗 문제 링크: https://www.acmicpc.net/problem/9335

9335번: 소셜 광고

 

---

📝 문제 요약

• 모든 사용자가 광고를 볼 수 있도록 게시할 최소의 광고의 수 계산
• 친구의 광고는 시청 할 수 있다
• A와 B가 친구 이면 B도 A와 친구이다
• A와 B, B와 C가 친구 여도 A와 C는 친구가 아닐 수 있다

---

🧷 문제 분류

• 브루트포스
• 비트마스킹

  ---

  
  

📦 제출 정보

🔗 소스코드: GitHub - cbkpar/BOJ/boj_9335.cpp

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
93841857	cbkpar	9335	맞았습니다!!	2020 KB	96 ms	C++17	899 B

---

💻 코드 (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

	int iT;
	cin >> iT;
	for (int t = 1; t <= iT; ++t)
	{
		int iN;
		cin >> iN;

		vector<int> vecNum(iN, 0);
		for (int i = 0; i < iN; ++i)
		{
			int iFriend;
			cin >> iFriend;
			vecNum[i] = 1 << i;
			for (int j = 0; j < iFriend; ++j)
			{
				int iFriendNum;
				cin >> iFriendNum;
				vecNum[i] |= (1 << (iFriendNum - 1));
			}
		}

		int iAns = iN;
		for (int i = 0; i < (1 << iN); ++i)
		{
			int iTemp = i;
			int iCount = 0;
			int iConnected = 0;
			for (int j = 0; j < iN; ++j)
			{
				if (iTemp % 2 == 1)
				{
					++iCount;
					iConnected |= vecNum[j];
				}
				iTemp /= 2;
			}

			if (iConnected == (1 << iN) - 1)
			{
				iAns = min(iAns, iCount);
			}
		}

		cout << iAns << "\n";
	}
	return 0;
}

 

---

💡 풀이 방법

🔍 문제 접근

• 각 사람의 광고 도달 범위를 비트마스크로 표현합니다.
• 전체 사람을 0부터 N-1까지 인덱스로 보고, 각 인덱스마다 자신과 친구들이 도달 가능한 사람을 비트로 나타냅니다.

🧠 핵심 아이디어

• vecNum[i]는 i번째 사람이 광고를 본다면, 영향을 받는 사람들의 집합을 비트마스크로 표현한 것입니다.
• 이후 가능한 모든 사람 선택의 조합 (2^N개)을 순회하며, 해당 조합으로 광고를 보낼 경우 전체 사람에게 도달 가능한지 확인합니다.
• 전체 사람에게 도달할 수 있는 최소 사람 수를 구하는 것이 목표입니다.

⚙️ 구현 방식

1. 각 사람에 대해 자신을 포함한 친구 목록을 비트마스크로 구성
2. 비트마스크 조합 (0부터 2^N-1까지) 을 순회하면서 해당 조합으로 도달 가능한 사람들을 계산
3. 모든 사람에게 도달할 수 있다면 (즉, 비트 OR 결과가 (1 << N) - 1), 최소 인원 수를 갱신

✅ 시간 복잡도

• 총 조합 수는 2^N이며, 각 조합에 대해 N번 반복 → O(N × 2^N)
• N ≤ 20 이하이므로 브루트포스로 충분히 해결 가능

 

---

🧪 예제 입력 / 출력

📘 예제 1

입력

2
5
4 2 3 4 5
4 1 3 4 5
4 1 2 4 5
4 1 2 3 5
4 1 2 3 4
5
2 4 5
2 3 5
1 2
2 1 5
3 1 2 4

출력

1
2