백준 1043: 거짓말 [C++]

https://www.acmicpc.net/problem/1043

 

거짓말쟁이가 되기시러

각 파티의 참여자를 서로 연결하고, 타고타고 올라갔을때 진실을 아는 사람을 만나는지 안 만나는지를 확인해야 한다. 연결하고 찾는데는 유니온파인드를 사용한다.

보자마자 이거다 하고 생각이 안 났다.. 사실 지금도 잘은 모르겠다 첨엔 걍 단순히 진실을 아는 사람이 파티에 섞여있는가를 따지는 문제인가 싶었는데, 같은 사람이 다른 파티에 참여해 다른 사실을 듣는 것 역시 안 된다는 조건 때문에 유니온파인드를 사용해줘야 했다.

 

우선 유니온파인드 구현은 언제나와 같다.

vector<int>parent;

int findParent(int node) {
    if (parent[node] < 0) {
        return node;
    }
    return parent[node] = findParent(parent[node]);
}

// Union two sets
void unionInput(int x, int y) {
    int xp = findParent(x);
    int yp = findParent(y);
    if (xp == yp) return; // 이미 같은 집합에 속해 있다면 return
    if (parent[xp] < parent[yp]) {
        swap(xp, yp);
    }
    parent[yp] += parent[xp];
    parent[xp] = yp;
}

 

입력으로 진실을 아는 사람들이 주어진다. 이 사람들을 know_truth라는 배열에 따로 저장해준다.

for(int i=0;i<truth_cnt;i++){
        cin >> know_truth[i];
    }

 

이제 각 파티의 참여자 정보가 주어진다. 벡터형태로 여러 개 주어질 것이므로 이차원벡터로 저장해준다.

vector<vector<int>> parties(m, vector<int>(n+1, 0));
    for(int i=0;i<m;i++){
        cin >> party_size;
        parties[i].resize(party_size);
        for(int j=0;j<party_size;j++){
            cin >> parties[i][j];
        }
    }

 

각 파티의 사람들은 하나의 집합으로 연결되어야 한다. union을 수행해주자.

for(auto party: parties){
        for(int j=1;j<party.size();j++){
            unionInput(party[0], party[j]);
        }
    }

 

연결을 다 했으면 이제 진실을 아는 사람들과 연결점이 있는지 찾아줘야 한다.

그러기 위해서는 먼저 진실을 아는 사람들도 하나의 집합으로 연결되어야 할 필요가 있다.

for(int i=1;i<truth_cnt;i++){
        unionInput(know_truth[0], know_truth[i]);
    }

이렇게 연결된 후, 진실을 아는 사람들이 연결된 집합의 루트를 찾아준다. findParent를 쓰면 되지만 진실을 아는 사람이 0명 주어질 수도 있으므로, 그럴 경우에는 초기값인 -1을 할당해준다

int truth_root = know_truth.empty() ? -1 : findParent(know_truth[0]);

 

이제 주어진 파티에서 과장해 말할 수 있는지 체크해준다.

먼저 true로 설정한 뒤, 각 파티 내에서 반복문을 돌며 노드의 부모를 찾아주고, 해당 부모가 진실을 아는 사람 집단의 루트(truth_root)와 같은지 확인해준다. 같다면 언젠가는 이 사람은 진실을 알게 될 것이므로 false로 바꿔준다. 한 명만 false로 판명나도 그 파티에서는 과장해 말할 수 없으므로 반복을 탈출해준다.

한 파티에서 검사가 끝난 뒤에도 flag가 여전히 true라면 그 파티에서는 과장해도 되므로 answer 값을 증가시킨다.

이 과정을 모든 파티에 대해 반복한다.

int answer = 0;
    for(auto party:parties){
        bool flag = true; //해당 파티에서 과장할 수 있는지
        for(auto p : party){
            if(findParent(p) == truth_root){
                flag = false; //해당 노드의 부모가 진실을 아는 집단의 부모와 동일 => 과장할 수 없음
                break;
            }
        }
        if(flag) answer++;
    }

 

전체 코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

vector<int>parent;

int findParent(int node) {
    if (parent[node] < 0) {
        return node;
    }
    return parent[node] = findParent(parent[node]);
}

// Union two sets
void unionInput(int x, int y) {
    int xp = findParent(x);
    int yp = findParent(y);
    if (xp == yp) return; // 이미 같은 집합에 속해 있다면 return
    if (parent[xp] < parent[yp]) {
        swap(xp, yp);
    }
    parent[yp] += parent[xp];
    parent[xp] = yp;
}

int main(){
    int n, m, truth_cnt, party_size;
    cin >> n>> m >> truth_cnt;
    parent.assign(n+1, -1);
    vector<int> know_truth(truth_cnt); //진실을 아는 사람들
    
    for(int i=0;i<truth_cnt;i++){
        cin >> know_truth[i];
    }
    
    //파티 참여자 정보 입력
    vector<vector<int>> parties(m, vector<int>(n+1, 0));
    for(int i=0;i<m;i++){
        cin >> party_size;
        parties[i].resize(party_size);
        for(int j=0;j<party_size;j++){
            cin >> parties[i][j];
        }
    }
    
    //각 파티의 사람들을 한 집합으로 union
    for(auto party: parties){
        for(int j=1;j<party.size();j++){
            unionInput(party[0], party[j]);
        }
    }
    
    for(int i=1;i<truth_cnt;i++){
        unionInput(know_truth[0], know_truth[i]);
    }
    int truth_root = know_truth.empty() ? -1 : findParent(know_truth[0]);
    
    int answer = 0;
    for(auto party:parties){
        bool flag = true; //해당 파티에서 과장할 수 있는지
        for(auto p : party){
            if(findParent(p) == truth_root){
                flag = false; //해당 노드의 부모가 진실을 아는 집단의 부모와 동일 => 과장할 수 없음
                break;
            }
        }
        if(flag) answer++;
    }
    cout << answer;
    return 0;
    
    
}