BOJ : https://www.acmicpc.net/problem/1043
게시판을 보니 문제를 이해를 못하시는 분들이 꽤 되시는 것 같아서 문제 설명부터 하겠습니다.
간략하게 설명하자면,
진실을 아는 사람을 A, A가 속한 파티에 있는 사람을 B 라고 할 때
A,B 가 속한 모든 파티에서 거짓을 말하면 안됩니다.
결국 어떤 파티에서 A가 속하게 되면 => 이 파티 뿐만 아니라 다른 파티에서도 A, B 의 유무를 확인해야 됩니다.
예제를 보면
1 2
3
2 3 4
진실을 아는 사람이 만약 0이면 그냥 말그대로 파티 아무데서나 거짓말을 해도 된다가 되지만
만약 여기서 진실을 아는 사람이 2 이면?
파티1은 제외되고 일단 사람2가 파티2, 3에도 존재하는지 확인해봅니다.
파티2에는 사람3밖에 없으므로 거짓을 해도 됩니다. (아직까지는)
파티3에는 사람2가 존재하게 됩니다. => 나머지 사람 3, 4 가 참석할 다른 파티를 확인합니다.
사람3부터 확인하면 사람3은 파티2에 존재합니다. 결국 파티2는 거짓을 하면 안되게 됩니다.
이런방향으로 흘러가는 문제입니다.
처음에는 dfs를 통해서 짜보려고 했는데, 구현력이 떨어져서인지 구현이 잘 안되길래 bfs로 변경했습니다.
우선적으로 진실을 아는 사람을 모든 파티에 대해 확인할 때,
진실을 아는 사람이 파티에 참가하면 그 파티에 있는 사람까지 큐에 넣었습니다.
이 작업이 끝나면 큐에서 하나하나 꺼내면서 모든 파티를 확인해주시면 됩니다.
|
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
|
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <string>
using namespace std;
int person, party, know;
vector<int> know_person;
bool party_person[52][52];
bool visit[52][52];
bool dont_party[52];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> person >> party >> know;
for (int i = 0; i < know; i++) {
int n; cin >> n; know_person.push_back(n);
}
for (int i = 0; i < party; i++) {
int n; cin >> n;
for (int j = 0; j < n; j++) {
int m; cin >> m; party_person[i][m] = true;
}
}
queue<pair<int, int> > q;
if (know == 0) cout << party;
else {
for (int i = 0; i < party; i++) {
for (int j = 0; j < know; j++) {
if (party_person[i][know_person[j]]) {
for (int k = 0; k < 52; k++) {
if (party_person[i][k])
q.push({ i,k });
}
}
}
}
while (!q.empty()) {
int party_idx = q.front().first;
int p = q.front().second;
q.pop();
if (visit[party_idx][p]) continue;
visit[party_idx][p] = true;
dont_party[party_idx] = true;
for (int i = 0; i < party; i++) {
if (party_person[i][p]) {
for (int j = 0; j < 52; j++) {
if (party_person[i][j]) q.push({ i,j });
}
}
}
}
int cnt = 0;
for (int i = 0; i < party; i++) {
if (dont_party[i] == false) cnt++;
}
cout << cnt;
}
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
'algorithm > BOJ' 카테고리의 다른 글
| BOJ 14503번 로봇 청소기 (0) | 2020.03.13 |
|---|---|
| BOJ 3709번 레이저빔은 어디로 (0) | 2020.03.13 |
| BOJ 1074번 Z (0) | 2020.03.05 |
| BOJ 1026번 보물 (0) | 2020.02.28 |
| BOJ 2240번 자두나무 (0) | 2020.02.26 |