[백준 C++] 1043번: 거짓말 (두가지 풀이queue, union&find)

1.문제

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

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

2. Solved.ac 난이도

3. 활용 알고리즘:  Queue 이용 or Union & Find(그래프)

4. callout: 

처음 봤을때 union&find를 써야한다는 생각을 하지 못해 큐로 풀었다
워낙 n이 작기도 하고 큐로 금방금방 pop하면서 풀면 거의 nlogn정도로 풀 수 있는 듯!

---

풀이 1. (Queue 이용)

그냥 사람별 가는 파티 저장한 큐, 파티별 방문하는 사람 저장한 큐 이렇게 두개로 반복문을 돌리면서

비밀을 알고 있는 know 큐에 대한 푸시와, 파티 방문하는 사람 큐에 대한 팝으로 구현

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
queue<int> person[51];
queue<int> party[51];
queue<int> know;


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

    int n, m;
    cin >> n >> m;
    int k_cnt;
    cin >> k_cnt;
    int val;
    for (int i = 0; i < k_cnt; i++) {
        cin >> val;
        know.push(val);
    }
    int p_cnt;

    for (int i = 0; i < m; i++) {
        cin >> p_cnt;
        for (int j = 0; j < p_cnt; j++) {
            cin >> val;
            party[i].push(val);
            person[val].push(i);
        }
    }

    while(!know.empty()){
        int p=know.front();
        know.pop();
        while(!person[p].empty()){
            int pt=person[p].front();
            person[p].pop();
            while(!party[pt].empty()){
                know.push(party[pt].front());
                party[pt].pop();
            }
        }
    }

    int cnt = 0;
    for (int i = 0; i < m; i++) {
        if (party[i].size()!=0) {
            cnt++;
        }
    }
    cout << cnt;
    return 0;
}

 

풀이 2. Union&Find

union and find로 구현한 코드

같은 파티를 가는 사람끼리 union, 비밀을 알고 있는 사람끼리 union 을 진행해서 해당 파티에 가는 사람중 한명과 비밀을 알고 있는 사람중 한명의 parent값이 같을 경우 해당 파티는 모두 비밀을 알고 있는 것으로 여긴다!

#include<iostream>

#include<algorithm>

#include<vector>
using namespace std;
vector<int> person[51];
vector<int> party[51];
int par[51];

int find(int a) {
	if (par[a] == a) return a;
	return par[a] = find(par[a]);
}

void uni(int a, int b) {
	int pa = find(a);
	int pb = find(b);

	par[pa] = pb;
}

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

	int n, m;
	cin >> n >> m;
	for (int i = 0; i <= n; i++) {
		par[i] = i;
	}
	int k_cnt;
	cin >> k_cnt;
	int val, val2;
	val = 0;
	if (k_cnt != 0) {
		cin >> val;
	}
	for (int i = 1; i < k_cnt; i++) {
		cin >> val2;
		uni(val, val2);

		
	}
	int p_cnt;

	for (int i = 0; i < m; i++) {
		cin >> p_cnt;
		for (int j = 0; j < p_cnt; j++) {
			cin >> val2;
			party[i].push_back(val2);
		}
	}

	int cnt = 0;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < party[i].size(); j++) {
			uni( party[i][j], party[i][0]);
		}
	}

	int pval = find(val);
	for (int i = 0; i < m; i++) {
		int ppar = find(party[i][0]);
		if (pval != ppar) {
			cnt++;
		}
	}
	cout << cnt;
	return 0;
}