백준 1043 거짓말
백준 1043
이 문제는 지민이가 과장된 이야기를 할 수 있는 파티의 갯수를 구하는 문제이다. 이 때 지민이의 이야기의 진실을 알고 있는 사람이 주어지고 각 파티에 어떤 사람들이 오는지가 번호로 주어진다.
이 문제를 풀기 위해서는 결국 진실을 알고 있는 사람이 속한 파티들을 제외한 파티의 갯수가 답이 되게 된다.
어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 과장된 이야기를 할 수 없기 때문에
=> 결국 여러 파티에 겹처서 온 사람이 진실을 알고 있다면 그 사람이 속한 여러 파티들을 다 제외해줘야 한다는 뜻이다. 그러기 위해서 한 사람이 여러 파티에 속했다면 그 파티들을 모두 하나의 집합으로 만들 필요가 이다
이 때 union-find를 이용해서 집합을 만들었다.
진실을 아는 사람을 따로 하나의 벡터에 다 담아두고
파티들을 하나의 벡터 배열에 담아둔다.
그리고 각 파티마다 진실을 아는 사람이 있는지 확인을 해주면 된다
=> find 함수를 이용해서 진실을 아는 사람의 부모와 각 파티에 속한 사람들의 부모가 같은지 확인해주면 된다.
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<int> truth;
vector<int> party[51];
int parent[51];
int find(int x) {
if (parent[x] == x) return x;
else return parent[x] = find(parent[x]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
else {
if (x > y) parent[x] = y;
else parent[y] = x;
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) parent[i] = i;
int t;
cin >> t;
while (t--) {
int x;
cin >> x;
truth.push_back(x);
}
int cnt = 0;
for (int i = 0; i < m; i++) {
int x;
int flag = 0;
cin >> x;
if (x >= 1) {
for (int j = 0; j < x; j++) {
int y;
cin >> y;
party[i].push_back(y);
if (j != 0) merge(party[i][0], y);
}
}
}
for (int j = 0; j < m; j++) {
int flag = 0;
for (int k = 0; k < party[j].size(); k++) {
for (int i = 0; i < truth.size(); i++) {
if (find(truth[i]) == find(party[j][k])) {
cnt++;
flag = 1;
break;
}
}
if (flag) break;
}
}
cout << m - cnt << '\n';
}
Author And Source
이 문제에 관하여(백준 1043 거짓말), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@supway/백준-1043-거짓말저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)