[알고리즘] 백준 1043 거짓말

상당히 고생했던 문제이다. 유니온 파인드라는 알고리즘을 알지 못해서 해결방법을 떠올리지 못했다.

개요

진실을 알고 있는 사람들과 같은 파티에 있는 사람들은 모두 진실을 알고 있는 사람들과 같게 된다.

풀이

처음에는 거짓말 할 수 있는 파티를 1, 없는 파티를 0으로 두어 모든 경우의 수를 탐색하려 했다. 그러니 시간 복잡도가 O(2^n)이 되어 버려 n<50인 이번 문제를 해결하지 못한다.

그러나 res변수를 파티수로 잡고 거짓말 하지 못하는 파티를 찾아내면 그 값을 -1하는 방식으로 해결하면 시간 복잡도가 O(n^3)이 되어 문제를 해결 할 수 있다.

소스코드

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <vector>

using namespace std;

int parent[51];
vector<int> knowing;
vector<vector<int> > party(50);
int res,n,m,val = 0;

int Find(int x) {
    if (parent[x] == x)
        return x;
    return x = Find(parent[x]);
}

void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    parent[x] = y;
}

int answer() {
    int res = m;
    for(const vector<int> &people : party) {
        bool flag = false;
        for(const int &person : people) {
            if(flag) break; 
            for(const int &know : knowing) {
                if(Find(person) == Find(know)) {
                    flag = true;
                    break;
                }
            }
        }
        if(flag) {
            res--;
        }
    }
    return res;
}

int main() {
    scanf("%d %d",&n,&m);
    int tmp; 
    scanf("%d",&tmp);
    int a;
    for(int i = 0;i<n;i++) {
        parent[i] = i;
    }
    for(int i = 0;i<tmp;i++) {
        scanf("%d",&a);
        knowing.push_back(a);
    }
    for(int i = 0;i<m;i++) {
        scanf("%d",&tmp);
        int num,prev;
        for(int j = 0;j<tmp;j++) {
            if(j >= 1) {
                prev = num;
                scanf("%d",&num);
                Union(prev,num);
            }
            else {
                scanf("%d",&num);
            }
            party[i].push_back(num);
        }
    }
    printf("%d",answer());
}

참고

동준님의 블로그

사실상 코드를 배끼다시피 했다..😅 c++에서 foreach 문을 어떻게 쓰는지 몰랐었는데 이분 코드를 통해 알게되었다. c++11부터 지원하는 것 같다.