[백준 1043번] 거짓말

문제 링크: https://www.acmicpc.net/problem/1043

1043번: 거짓말

<문제 풀이> 그래프, 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++ 소스 코드>

#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;
}