[BOJ] 1043번 거짓말 (C++)

문제 (https://www.acmicpc.net/problem/1043)

1043번: 거짓말

유니온파인드로 해결한 문제이다.

 

1. 각 파티에 오는 사람들끼리 연결시킨다. (unionParent)

2. 전체 파티의 인원수만큼 반복문을 돌며 처음 입력받았던 진실을 아는 사람과 연결되었는지 확인한다. (findParent)

  2-1. 해당 파티에 진실을 아는 사람과 연결된 사람이 존재한다면? 그 파티에서는 거짓말을 할 수 없으므로 반복문 탈출

  2-2. 해당 파티에 진실을 아는 사람과 연결된 사람이 존재하지 않는다면? 정답 증가

 

가장 도움 되었던 반례! 문제 질문 페이지에 다른 분이 올려주신 건데 덕분에 잘못된 점을 찾았었다.

https://www.acmicpc.net/board/view/72203

---

[소스코드]

	/*
	BOJ 1043번: 거짓말
	2021-12-26
	Union-Find
	*/
	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	int getParent(int parent[], int x) {
	if(parent[x] == x) return x;
	return parent[x] = getParent(parent, parent[x]);
	}
	void unionParent(int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if(a < b) parent[b] = a;
	else parent[a] = b;
	}
	int findParent(int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if(a == b) return 1;
	else return 0;
	}
	int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	vector<int> truth, tmp;
	vector<vector<int>> party;
	int n, m, truthNum; //사람 수, 파티 수, 진실을 아는 사람의 수
	int total, num, ans = 0;
	bool flag;
	cin >> n >> m >> truthNum;
	if(truthNum == 0) { // 진실을 아는 사람이 한 명도 없을 때
	cout << m;
	return 0;
	}
	int parent[n + 1];
	for(int i = 1 ; i <= n ; i++) parent[i] = i;
	for(int i = 0 ; i < truthNum ; i++) {
	cin >> num;
	truth.push_back(num); // 진실을 아는 사람들의 번호
	}
	for(int i = 0 ; i < m ; i++) {
	cin >> total;
	for(int j = 0 ; j < total ; j++) {
	cin >> num;
	tmp.push_back(num);
	}
	party.push_back(tmp);
	for(int j = 1 ; j < tmp.size() ; j++) unionParent(parent, tmp[j - 1], tmp[j]);
	tmp.clear();
	}
	for(int i = 0 ; i < party.size() ; i++) {
	flag = true;
	for(int j = 0 ; j < party[i].size() ; j++) {
	for(int k = 0 ; k < truth.size() ; k++) {
	if(findParent(parent, party[i][j], truth[k])){
	flag = false;
	break;
	}
	if(!flag) break;
	}
	}
	if(flag) ans++;
	}
	cout << ans;
	return 0;
	}

view raw 1043.cpp hosted with ❤ by GitHub

---

2021-12-26

Gold 4

- 그래프 이론

- 자료 구조

- 그래프 탐색

- 분리 집합