백준 1043: 거짓말

문제 요약

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

사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다. 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.

문제 분류

• 자료 구조
• 그래프 이론
• 그래프 탐색
• 분리 집합

문제 풀이

각 파티의 사람들을 하나의 집합으로 파악하고, 진실을 아는 사람들끼리도 따로 집합으로 만들면 된다. 즉, 먼저 진실을 아는 사람들끼리 하나의 집합을 만들고, 그 루트를 0으로 삼는다. 사람의 번호는 1부터 세기 때문에 0번을 사용할 수 있다고 생각했다. 결국, 루트가 0인 사람은 진실을 아는 사람일 것이다. 그 후 각 파티의 사람들을 집합으로 묶는다. 그 안에 진실을 아는 사람이 섞여있을 경우 해당 집합의 루트는 0이 되어, 반드시 진실을 말해야 한다. 반대로 진실을 아는 사람이 없을 경우에 그 집합의 루트는 0이 아니므로 그때는 거짓말을 해도 된다.

서로 다른 두 집합을 병합할 경우, 어느 한 쪽의 루트 0이라면 반드시 그 0을 루트로 삼아야한다. 그리고 각 파티마다 첫번째 사람을 기준으로 삼아서, 그 사람을 기준으로 파티의 집합을 만들었다. 그 후 vector에 삽입해주었는데, 마지막에 vector를 모두 순회하면 각 파티마다의 진실을 아는 사람이 있는지 없는지를 파악할 수 있다. 즉, 그 사람이 속한 집합의 루트가 0이라면 그 파티에는 반드시 진실을 말해야 하고, 그렇지 않으면 거짓말을 해도 된다. 그렇게 카운트해서 출력해주었다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>

using namespace std;

int p[50];

int find(int n) {
	if (p[n] < 0) return n;
	p[n] = find(p[n]);
	return p[n];
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	if (b == 0) {
		p[b] += p[a];
		p[a] = b;
	}
	else {
		p[a] += p[b];
		p[b] = a;
	}
}

int main()
{
	int n, m, tcnt, pos, in, cnt = 0;
	vector<int> v;
	memset(p, -1, sizeof(p));
	scanf("%d%d", &n, &m);
	scanf("%d", &tcnt);
	for (int i = 0; i < tcnt; i++) {
		scanf("%d", &in);
		merge(0, in);
	}
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &tcnt, &pos);
		for (int j = 1; j < tcnt; j++) {
			scanf("%d", &in);
			merge(pos, in);
		}
		v.push_back(pos);
	
	}
	for (auto& it : v)
		if (find(it) != 0) cnt++;
	cout << cnt;
}