최신 글
10
제목 게시일
30

[백준] 1043번 : 거짓말

profile
코우
2021-08-17 04:14
조회 수 : 1118

출처 : 백준

문제 보러가기 : 
거짓말

해당 문제는 깊이우선탐색(DFS)을 이용해서 풀 수 있는 문제이다.

필요한 배열
  • 진실을 아는 사람(kpeople) - bool
  • 진실을 말한 파티를 저장하는 배열(kparty) - bool
  • 파티별 참여하는 사람(party) - int형 2차원 배열
  • 사람별 참여하는 파티를 저장하는 배열(people) - int형 2차원 배열

초기에 주어지는 진실을 아는 사람을 kpeople에 체크한다.
그 후 각 파티에 참여하는 사람, 사람별 참여하는 파티를 각각 party, people에 저장한다.


로직

진실을 아는 사람을 기점으로 그 사람이 참여한 파티를 kparty에 체크하고 해당 파티에 참석한 사람을 kpeople에 체크한다.
(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
share
twitter facebook kakao naver
댓글