[백준/boj] 1043번: 거짓말 | C++

dfs - 그래프 풀듯이

벡터로 만든 리스트 형식 사용

(정석풀이는 아니라고 함. 정석은 유니온 파인드? 아직 모르는 알고리즘이라 공부해야겠다!)

 

1. 진실을 아는 사람들 번호 -> knowMem 스택에 담고, 방문처리(vis[번호] =1;)

2. [멤버별 속해있는 파티] 와 [파티별 속해있는 사람들] 을 리스트형식 벡터 배열로 선언
3. [멤버별 속해있는 파티]배열을 돌면서 [파티별 속해있는 사람들] 배열을 돌아(이중for문)
    3-1) vis[멤버번호] ==0 -> 스택에 담아, vis =1;
4. 진실 아는 사람이 속한 파티 번호들을 set에 저장하여 최종으로 m-set배열사이즈 로 답 구함

stack<int> knowMem;//처음에 진실 알고있던사람 번호, 그로인해 진실 새로 알게된 사람 번호 저장
vector<int> memPartyList[52]; //멤버별로 어디 파티에 속해있나 | 진실 아는 사람들 번호 = key, 그 사람들이 속한 그룹 번호 = value
vector<int> groupPeople[52]; //파티별 속해있는 사람들
set<int> trueParty; //진실을 아는 사람이 속해있는 파티번호들 저장 (set으로 선언해 중복 제거)
int vis[52];//각 사람들 번호를 인덱스로 관리

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<set>
using namespace std;

int n,m,k;

stack<int> knowMem;//처음에 진실 알고있던사람 번호, 그로인해 진실 새로 알게된 사람 번호 저장
vector<int> memPartyList[52]; //멤버별로 어디 파티에 속해있나 | 진실 아는 사람들 번호 = key, 그 사람들이 속한 그룹 번호 = value
vector<int> groupPeople[52]; //파티별 속해있는 사람들
set<int> trueParty; //진실을 아는 사람이 속해있는 파티번호들 저장 (set으로 선언해 중복 제거)
int vis[52];//각 사람들 번호를 인덱스로 관리

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

    cin >>n>>m>>k;

    while(k--){ //최초로 진실 아는 사람들 저장 
        int x;
        cin >>x;
        knowMem.push(x);
        vis[x]=1;
    }

    for(int i=0;i<m;i++){ // 순서대로 파티 0,1,2.. 으로함
        int t;
        cin >>t;
        while(t--){
            int c;
            cin>>c;
            groupPeople[i].push_back(c); //파티별로 누가 있나 저장
            memPartyList[c].push_back(i); //멤버별로 어디 파티에 속해있나 저장
        }
    }
    
    while(!knowMem.empty()){ 
        int cur = knowMem.top(); knowMem.pop();

        for(auto i:memPartyList[cur]){ //진실 아는 멤버가 속한 파티들 리스트 돌기
            trueParty.insert(i); //진실 말해야하는 파티 번호 저장
            for(auto j : groupPeople[i]){//그 파티에 속한 멤버들이 누가있나 리스트 돌기
                if(vis[j]==0){ //진실을 아는 사람이 새로 나타난 경우
                    knowMem.push(j);//그 사람 번호 스택에 저장하고
                    vis[j] =1;      //그 사람 번호 방문처리
                }
                
            }
        }

    }
    cout << m-trueParty.size();

}