[백준 1043번] 거짓말
문제 링크: https://www.acmicpc.net/problem/1043
1043번: 거짓말
지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민
www.acmicpc.net
<문제 풀이> 그래프, Union-Find (유니온- 파인드)
이 문제는 Union-Find 알고리즘을 이용하면 쉽게 풀 수 있습니다.
먼저 문제에 나온 테스트 케이스를 예시로 보면
4 3
0
2 1 2
1 3
3 2 3 4
위 그림에서 각 파티에 어떤 한 사람이라도 진실을 아는 사람이면 곧 그 파티에 존재하는 모든 사람은 진실을 아는 사람이 됩니다. 예제에서 진실을 아는 사람의 수가 0이므로 과장된 이야기를 할 수 있는 파티의 개수는 3이 됩니다.
만약에 진실을 아는 사람이 2번이라고 해보겠습니다. 그러면 입력은 다음과 같이 주어집니다.
4 3
1 2
2 1 2
1 3
3 2 3 4
그러면 처음에 2번 사람이 진실을 아는 사람이니깐 2번 사람으로부터 바이러스가 퍼지듯이 연결된 모든 사람이 진실을 아는 사람이 됩니다.
이때 답은 0이 됩니다.
그러면 결국 각 파티마다 입력되는 사람들을 같은 그래프로 묶고, 진실을 아는 사람과 같은 그래프에 있는지만 확인하면 됩니다.
같은 그래프로 묶는건 Union, 같은 그래프에 속해 있는지 판별하는 건 Find을 이용하면 됩니다.
<C++ 소스 코드>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
#include <iostream>
#include <vector>
using namespace std;
int n, m, k;
int parents[51];
vector<int> know;
vector<vector<int> > v(50);
int Find(int x) {
if (parents[x] == x) return x;
return x = Find(parents[x]);
}
void Union(int x, int y) {
x = Find(x);
y = Find(y);
parents[x] = y;
}
int main(void) {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m >> k;
while (k--) {
int t;
cin >> t;
know.push_back(t);
}
for (int i = 1; i <= n; i++) parents[i] = i;
for (int i = 0; i < m; i++) {
int p;
cin >> p;
int num;
int prev;
for (int j = 0; j < p; j++) {
if (j >= 1) {
prev = num;
cin >> num;
Union(prev, num);
}
else {
cin >> num;
}
v[i].push_back(num);
}
}
for (auto& list : v) {
bool flag = false;
for (auto& person : list) {
if (flag) break;
for (auto& t : know) {
if (Find(person) == Find(t)) {
flag = true;
break;
}
}
}
if (flag)m--;
}
cout << m;
return 0;
}
|
cs |