[BOJ] 백준 1043번 - 거짓말 풀이

| |
백준 온라인 저지 백준 1043번 - 거짓말 C++ 풀이


문제

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.

사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다. 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.


입력

첫째 줄에 사람의 수 N과 파티의 수 M이 주어진다.

둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다. 사람들의 번호는 1부터 N까지의 수로 주어진다.

셋째 줄부터 M개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.

N, M은 50 이하의 자연수이고, 진실을 아는 사람의 수와 각 파티마다 오는 사람의 수는 모두 0 이상 50 이하의 정수이다.


출력

첫째 줄에 문제의 정답을 출력한다.


풀이

유니온 파인드 자료구조를 이용해 해결할 수 있는 상호배타적 집합 문제이다. 초기에 진실을 알고 있는 사람들의 집합을 구해놓는다. 파티 인원들을 입력받은 후에는 같은 파티에 참가하는 사람들을 모두 같은 집합으로 union 시킨다. 이 과정을 거치면 진실을 알고 있는 사람들과 같은 파티에 참석하는 모든 사람들은 진실을 알고 있는 사람들의 집합에 속해있게 된다. 한 파티에서 한 명이라도 위 집합에 속해있으면 파티원 전체가 속해있으므로 모든 파티에서 임의의 인원 1명을 조사하여 진실을 알고 있는 사람들의 집합에 속해있는지 아닌지 확인하면 답을 구할 수 있다.


전체 코드

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
#include <vector>
#include <iostream>
using namespace std;

struct Unionfind{
    vector<int> parent, rank;
    Unionfind(int n){
        parent=vector<int>(n+1);
        for(int i=1;i<=n;i++)
            parent[i] = i;
        rank=vector<int>(n+1,1);
    }
    int ufFind(int n){
        if(parent[n] == n) return n;
        return parent[n] = ufFind(parent[n]);
    }
    void ufUnion(int a, int b){
        a = ufFind(a), b = ufFind(b);
        if(a == b) return;
        if(rank[a] <= rank[b]){
            parent[a] = b;
            if(rank[a] == rank[b]) rank[b]++;
        }
        else parent[b] = a;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N,M; cin>>N>>M;

    Unionfind uf(N);

    int K; cin>>K;
    if(K==0) {cout<<M; return 0;} // 진실을 아는 사람이 아무도 없을 경우

    vector<int> know(K);
    for(int& i:know) cin>>i;
    if(know.size()>1)
        for(int i=1;i<K;i++)
            uf.ufUnion(know[0],know[i]);

    vector<int> party[50];
    for(int i=0;i<M;i++){
        int s; cin>>s;
        party[i] = vector<int>(s);
        for(int& p:party[i]) cin>>p;
        for(int j=1;j<party[i].size();j++)
            uf.ufUnion(party[i][0],party[i][j]);
    }

    int ans=0;
    for(int i=0;i<M;i++)
        if(uf.ufFind(know[0]) != uf.ufFind(party[i][0]))
            ans++;

    cout<<ans;
    return 0;
}
0%