백준 1043 c++ "거짓말" -PlusUltraCode-

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

 

 

[필자 사고]

필자는 이 문제를 유니온 파인드로 접근했다.

 

하지만 많은 시행 착오가 있었다. 필자의 사고 과정은 아래와 같다.

예를들어 1,2,3 번은 진실을 알고 있는 사람이라고 가정하자

 

만약 5번째 파티에 1, 6, 10 번의 사람들이 올 경우 6하고 10번 또한 진실을 듣게 되므로

필자는 아싸리 1,2,3, 6 ,10 을 같은 집합으로 만들었다.

 

의도는 좋았으나 순서의 문제가 생겼다.

 

필자는 첫번째 파티부터 마지막파티까지 순서대로 위와 같은 과정을 거쳤는데 

만약 마지막 파티에 위와 같은 경우가 생길경우 6번하고 10번이 들어간

첫번째 파티가 있을경우 문제가 생긴다.

 

첫 번째 파티에는 4 ,5 ,6 의 사람들이 있다라고 가정하면 4번하고 5번또한 같은 집합으로 했어야 됬는데

순서상의 이유로 지나치게 되는 문제가 발생했다.

 

필자는 이 문제를 해결하기 위해 아래와 같은 방법으로 해결했따.

첫번째 파티는 첫번째 집합

두 번째 파티는 두번째 집합

......

열 번째 파티는 열번째 집합 이라 생각하고 각자 집합을 만들었고

 

마지막 검사때 그 집합에 원래 1,2,3과 같은 집합에 속하게 된다면 resultCount를 올리지 않고

반대가 되면 resultCount를 증가시키는 방법으로 문제를 해결 했다.

 

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

int N, M, P;
vector<vector<int>> peoples;
vector<int> knowPeoples;
vector<int> parent;

int find(int a) {
	if (a == parent[a])return a;
	return parent[a] = find(parent[a]);
}
void Union(int a, int b) {
	a = find(a);
	b = find(b);
	if (a != b) {
		parent[b] = a;
	}
}
bool checkSame(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)return true;
	return false;

}

void Input() {
	cin >> N >> M;
	parent.resize(N + 1);
	for (int i = 0; i <= N; i++) {
		parent[i] = i;
	}
	peoples.resize(M);


	cin >> P;
	if (P != 0) {
		for (int i = 0; i < P; i++) {
			int num;
			cin >> num;
			knowPeoples.push_back(num);
		}

		int firstNum = knowPeoples[0];
		for (int i = 0; i < P; i++) {
			Union(firstNum, knowPeoples[i]);
		}
	}

	for (int i = 0; i < M; i++) {
		int count;
		cin >> count;
		for (int k = 0; k < count; k++) {
			int num;
			cin >> num;
			peoples[i].push_back(num);
		}
	}
}

void GameStart() {
	for (int i = 0; i < M; i++) {
		for (int k = 0; k < peoples[i].size(); k++) {
			Union(peoples[i][0], peoples[i][k]);
		}
	}

	if (P == 0) {
		cout << peoples.size();
		return;
	}

	int resultCount = 0;

	for (int i = 0; i < M; i++) {
		int firstNum = knowPeoples[0];
		int secondNum = peoples[i][0];
		if (checkSame(firstNum, secondNum) == false) {
			resultCount++;
			continue;
		}
	}
	cout << resultCount;
}

int main(void) {
	Input();
	GameStart();
}