boj, 백준) 1043. 거짓말 ( C / C++)

1. 문제 링크

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

1043번: 거짓말

 

2. 문제 개요

지민이는 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기를 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또 다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.

 

사람의 수 N이 주어지고, 이야기의 진실을 아는 사람이 주어진다.

과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.

 

3. 문제 힌트

   순서는 상관없다. 진실을 아는 사람을 기점으로 진실이 퍼져나갈 것이다. 

BFS탐색을 이용해서 진실을 퍼뜨려 나가 보자.

 

 

4. 문제 풀기

정보를 입력받는데, 2가지로 분류해야 한다.

 

1개는 해당 파티에 속한 사람들의 번호.

1개는 해당 사람이 속한 파티들의 번호.

 

그리고 진실을 아는 파티들을 구별할 bool 배열.

이렇게 3가지의 Vector를 선언하자.

 

초기 Queue에는 진실을 알고 있는 사람을 넣는다.

Queue에서 진실을 알고 있는 사람을 한 명씩 꺼내면서,

그 사람이 속한 파티의 모든 사람들은 이제 진실을 알게 되니까 Queue에 넣어준다.

 

Queue가 비게 될 때까지위의 프로세스를 반복하고, 한 번도 방문하지 않은 파티의 수를 세어주자.

 

 

5. 코드

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

vector<vector<int>> party;
vector<vector<int>> adj;
vector<bool> visited;
int n, m, k;
queue<int> q;

int main()
{
	scanf("%d %d", &n, &m);

	adj.resize(n + 1);
	party.resize(m + 1);
	visited.resize(m + 1, false);

	scanf("%d", &k);
	for (int i = 0; i < k; ++i) {
		int val;
		scanf("%d", &val);
		q.push(val);
	}

	for (int i = 1; i <= m; ++i) {
		int cnt;
		scanf("%d", &cnt);
		for (int j = 0; j < cnt; ++j) {
			int val;
			scanf("%d", &val);
			party[i].push_back(val);
			adj[val].push_back(i);
		}
	}


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

		for (int i=0; i<adj[cur].size(); ++i)
		{
			int next = adj[cur][i];	//진실을 아는 사람이 속해있는 파티.
			//그 파티의 모두를 큐에 넣어야함.
			if (!visited[next]) {
				visited[next] = true;
				for (int j = 0; j < party[next].size(); ++j) {
					q.push(party[next][j]);
				}
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= m; ++i)
		if (!visited[i])	ans++;

	printf("%d", ans);

	return 0;
}

6. 결과 사진

 

지적, 댓글 언제나 환영입니다~