[baekjoon 백준] 1043 - 거짓말 : c++ 문제풀이

진실을 아는 사람과 그 사람과 파티에서 만난 적이 있는 사람이 있는 파티는 모두 제외해야 한다.
 
1. bfs
-> 노드끼리 연결 여부를 표시하는 map을 그려서 처음 주어진 진실을 아는 사람을 시작으로 bfs탐색을 돌린다.
연결 여부는 51*51 2차원 리스트로, 진실을 아는 사람은 1차원 리스트로 표현하고, 파티 참석자는 2차원 vector에 입력을 받았다.
 
코드->

#include <iostream>
#include <queue>
using namespace std;

bool map[51][51];
bool knowing[51];
vector<vector<int>> party;


int main() {
  //사람 수, 파티 수 입력 받기
  int person_num, party_num;
  cin >> person_num >> party_num;
  //최초 답 = 파티의 갯수
  int result = party_num;

  //진실 아는 사람 수와 사람 번호 받기
  int n,idx;
  cin >> n;
  //n이 0이면 바로 답 출력
  if (!n) {
    cout << result;
    return 0;
  }

  //진실 아는 사람의 번호를 받으면 서 큐에 넣고 knowing에 표시
  queue<int> q;
  for (int i =0; i<n; i++){
    cin >> idx;
    q.push(idx);
    knowing[idx] = true;
  }

  //파티 참석자 리스트 받기
  for (int i =0; i< party_num; i++){
    //사람 수
    cin >> n;
    //파티마다 첫 참석자가 root역할
    int root;
    vector<int> plist;
    for (int j =0; j< n; j++){
      cin >> idx;
      plist.push_back(idx);
      //root이후의 노드들 root와 연결
      if (j == 0) {
        root = idx;
        continue;
      }
      //연결여부 양방향으로 표시
      map[root][idx] = true;
      map[idx][root] = true;
    }
    party.push_back(plist);
  }

  //큐가 빌 때까지 bfs탐색 돌리기
  while(!q.empty()) {
    //큐에 담긴 노드들을 앞에서부터 빼면서 그 노드와 연결된 노드들 knowing에 표시
    int tmp;
    tmp = q.front();
    for (int i=1;i<=person_num;i++){
      if (map[tmp][i] && !knowing[i]){
        knowing[i] = true;
        q.push(i);
      }
    }
    q.pop();
  }
  //파티 참석자 리스트를 돌면서 knowing에 표시된 참석자가 있는 경우 result수를 감소시키고 다음 파티 참석자 리스트를 검사한다.
  for (int i =0;i<party_num;i++){
    for (int j=0;j<party[i].size();j++){
      if (knowing[party[i][j]]){
        result--;
        break;
      }
    }
  }
  
  cout << result;
  return 0;
}

   이렇게 해도 풀리긴 하는데, 어쨌든 queue에서 하나씩 뺄 때마다 전체 사람 수 만큼 탐색해야 하기 때문에 중복으로 탐색되는 노드도 많고 좀 더 효율적인 방법이 있을 거라고 생각했다.
 
 
그래서...!
2. union find로도 풀어보았다.
-> 진실을 아는 사람들을 집합으로 묶는다고 생각하면 된다. 
(사람을 노드로 취급) 초반에 모든 노드는 자기 자신이 root이고 각각 원소가 한 개인 집합들로 생각하면 된다.
그리고 b집합이 a집합에 포함되면 b집합의 root를 a의 root와 같은 것으로 표기하면서 병합(union)한다.
find는 재귀적으로 자신의 root의 root로 올라가면서 자신이 포함된 최종 root집합을 찾는 것이다. 
 
-> 예를 들어 1-2, 3-4, 2-3 연결되어 있고 1이 진실을 아는 경우일 때,

• 처음

사람 번호	1	2	3	4
루트	1	2	3	4

 

• 2를 1에 포함

사람 번호	1	2	3	4
루트	1	1	3	4

 

• 4를 3에 포함

사람 번호	1	2	3	4
루트	1	1	3	3

 

• 3을 2에 포함

사람 번호	1	2	3	4
루트	1	1	1	3

그럼 노드 4의 최종 루트를 찾는 find를 실행하면 3 -> 1로, 4노드가 1노드가 있는 집합에 포함되어 있다는 것을 찾을 수 있다.
위의 bfs보다 노드들을 연결하는 방식이 간단해진다. (입력 받을 때 바로바로 union을 실행할 수 있다.)
 
코드-> 

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

int root[51];
bool knowing[51];
vector<vector<int>> party;

int find(int n) {
  // root가 자기자신
  if (root[n] == n)
    return n;
  // root의 root 거슬러올라가 찾기
  root[n] = find(root[n]);
  return root[n];
}


void unionAB(int a, int b) {
  a = find(a);
  b = find(b);
  //uniong할 때 진실을 아는 집합이 있다면 그 집합을 기준으로 나머지 집합을 포함시킨다.
  if (knowing[b]) {
    root[a] = b;
  } else
    root[b] = a;
}


int main() {
  int person_num, party_num;
  //초기 집합 생성
  cin >> person_num >> party_num;
  int result = party_num;

  for (int i = 1; i <= person_num; i++) {
    root[i] = i;
  }

  int knowing_num, idx;
  cin >> knowing_num;
  for (int i = 0; i < knowing_num; i++) {
    int idx;
    cin >> idx;
    knowing[idx] = true;
  }

  int n;
  for (int i = 0; i < party_num; i++) {
    cin >> n;
    vector<int> plist;
    for (int j = 0; j < n; j++) {
      cin >> idx;
      plist.push_back(idx);
      if (j == 0) {
        continue;
      }
      //앞노드와 합집합 만들기
      unionAB(plist[j - 1], plist[j]);
    }
    party.push_back(plist);
  }

  for (int i = 0; i < party_num; i++) {
    for (int j = 0; j < party[i].size(); j++) {
      int r = find(party[i][j]);
      if (knowing[r]) {
        result--;
        break;
      }
    }
  }
  cout << result << endl;
  return 0;
}