출처 : 백준
문제 보러가기 : 거짓말
해당 문제는 깊이우선탐색(DFS)을 이용해서 풀 수 있는 문제이다.
필요한 배열
초기에 주어지는 진실을 아는 사람을 kpeople에 체크한다.
그 후 각 파티에 참여하는 사람, 사람별 참여하는 파티를 각각 party, people에 저장한다.
(kpeople은 관계가 끊어져 있을 수 있으므로 모든 kpeople에 관해서 로직을 반복한다.)
이후 해당 파티에 참여한 사람에 대하여 또 다시 위의 과정을 반복한다.
단, 각 로직마다 kparty, kpeople를 체크하여 중복되는 연산이 발생하는 것을 피해야 한다.
이렇게 모든 연관된 사람이 참석한 파티를 체크하면 체크되지 않은 파티는 거짓말을 할 수 있는 파티가 된다.
문제 보러가기 : 거짓말
해당 문제는 깊이우선탐색(DFS)을 이용해서 풀 수 있는 문제이다.
필요한 배열
- 진실을 아는 사람(kpeople) - bool
- 진실을 말한 파티를 저장하는 배열(kparty) - bool
- 파티별 참여하는 사람(party) - int형 2차원 배열
- 사람별 참여하는 파티를 저장하는 배열(people) - int형 2차원 배열
초기에 주어지는 진실을 아는 사람을 kpeople에 체크한다.
그 후 각 파티에 참여하는 사람, 사람별 참여하는 파티를 각각 party, people에 저장한다.
로직
(kpeople은 관계가 끊어져 있을 수 있으므로 모든 kpeople에 관해서 로직을 반복한다.)
이후 해당 파티에 참여한 사람에 대하여 또 다시 위의 과정을 반복한다.
단, 각 로직마다 kparty, kpeople를 체크하여 중복되는 연산이 발생하는 것을 피해야 한다.
이렇게 모든 연관된 사람이 참석한 파티를 체크하면 체크되지 않은 파티는 거짓말을 할 수 있는 파티가 된다.
소스코드
|
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
71
72
73
74
75
76
77
78
|
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
vector<bool> kpeople;
vector<bool> kparty;
vector<vector<int>> people;
vector<vector<int>> party;
void recursive(int truthParty) {
if (kparty[truthParty] == 0) {
kparty[truthParty] = 1;
for (int i = 0; i < party[truthParty].size(); i++) {
int p = party[truthParty][i];
if (kpeople[p] == 0) {
kpeople[p] = 1;
for (int j = 0; j < people[p].size(); j++) {
recursive(people[p][j]);
}
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int ans = 0;
int n, m, k ,p;
cin >> n >> m >> k;
party.resize(m+1);
people.resize(n+1);
kpeople.resize(n + 1);
kparty.resize(m + 1);
for (int i = 0; i < k; i++) {
cin >> p;
kpeople[p] = 1;
}
for (int i = 1; i <= m; i++) {
int psize;
cin >> psize;
for (int j = 0; j < psize; j++) {
cin >> p;
party[i].push_back(p);
people[p].push_back(i);
}
}
for (int i = 1; i <= n; i++) {
if (kpeople[i] == 1) {
for (int j = 0; j < people[i].size(); j++) {
if (kparty[people[i][j]] == 0) {
recursive(people[i][j]);
}
}
}
}
for (int i = 1; i <= m; i++) {
if (kparty[i] == 0)
ans++;
}
cout << ans << "\n";
return 0;
}
|
cs |
댓글