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

www.acmicpc.net/problem/1043

1043번: 거짓말

 

 

 

알고리즘 종류

자료구조

부분 집합

 

 

사고 과정

문제에서 제시된 예시를 가지고 손으로 풀이를 해보고 있었습니다. 파티에서 참가하는 사람들을 하나로 묶고 그중에서 한 명이 진실을 알면 파티에 갈 수 없다고 생각했습니다. 즉, 부분 집합을 만들면 될 것 같았습니다.

 

1. 인접 리스트(party)로 파티에 들어갈 사람들을 담습니다. 그리고 for문으로 파티를 돌면서 부분 집합을 만듭니다.

 

2. 파티를 for문으로 돌면서 부모(대표)를 가져옵니다. 그리고 for문으로 진실을 아는 사람들을 돌면서 파티의 대표와 진실을 아는 사람의 부모가 같은 지 확인 합니다.

 

3. '진실을 아는 사람의 부모'와 '파티의 부모'가 같다면, 그 파티에는 진실을 아는 사람이 포함되어 있는 것이므로 그 파티에 갈 수 없습니다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
 
using namespace std;
 
int n, m;
int ans;
 
int parents[51];
 
vector<int> party[51];
 
 
int get_parent(int a){
    if(parents[a] == a) return a;
    return parents[a] = get_parent(parents[a]);
}
 
 
void union_parents(int a, int b){
    a = get_parent(a);
    b = get_parent(b);
    
    if(a > b) parents[b] = a;
    else parents[a] = b;
}
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    ans = m;
    
    int k, v;
    vector<int > tmp;
    
    cin >> k;
    for(int i=0; i<k; i++){
        cin >> v;
        tmp.push_back(v);
    }
    
    for(int i=0; i<m; i++){
        cin >> k;
        for(int j=0; j<k; j++){
            cin >> v;
            party[i].push_back(v);
        }
    }
    
    for(int i=0; i<=n; i++) parents[i]= i;
    
    // 파티의 사람들을 부분 집합으로 묶기
    for(int i=0; i<m; i++){
        if(party[i].size() == 0) continue;
        
        int p = party[i][0];
        for(int j=0; j<party[i].size(); j++){
            union_parents(p, party[i][j]);
        }
    }
    
    // 파티를 돌면서 파티의 부모(대표)와 진실을 아는 사람이 같다면, 그 파티는 갈 수 없다. 
    for(int i=0; i<m; i++){
        if(party[i].size() == 0) continue;
        
        bool flag = true;
        
        int node1 = get_parent(party[i][0]);
        for(int j=0; j<tmp.size(); j++){
            int node2 = get_parent(tmp[j]);
            
            if(node1 == node2){
                flag = false;
                break;
            }
        }
        if(flag == false) ans--;
    }
    
    cout << ans << endl;
}

 

 

 

시행착오