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

문제

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

1043번: 거짓말

 

 

풀이

1. 유니온 파인드를 위한 대표 노드 자료구조를 초기화한다. (진실을 아는 사람 데이터, 파티 데이터)
2. 파티에 참석한 사람들을 1개의 집합으로 생각하고, 각각의 파티마다 union 연산을 이용해 사람들을 연결한다.
3. 각 파티의 대표 노드와 진실을 아는 사람들의 각 대표 노드가 동일한지 find 연산을 이용해 확인함으로써 과장된 이야기를 할 수 있는지 판단한다.

 

유니온 파인드(Union-Find) 알고리즘

유니온 파인드(Union-Find) 알고리즘

 

 

코드

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

int find_parent(int a);
void union_parent(int a, int b);
static vector<int> parent;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N, M;
  cin >> N >> M;

  int truth_count;
  cin >> truth_count;

  vector<int> truth_people(truth_count + 1);
  for(int i = 0; i < truth_count; i++)
  {
    cin >> truth_people[i];	// 진실을 아는 사람 저장
  }

  parent.resize(N + 1);
  for(int i = 0; i <= N; i++)
  {
    parent[i] = i;	// 대표 노드를 자기 자신으로 초기화하기
  }
  
  vector<vector<int>> party_people(M + 1);
  for(int party = 0; party < M; party++)
  {
    int party_count;
    cin >> party_count;

    int max_num, min_num;
    for(int p = 0; p < party_count; p++)
    {
      int person;
      cin >> person;
      party_people[party].push_back(person);	// 파티 데이터 저장

      max_num = 0;
      if(p >= 1)
      {
        max_num = max(parent[party_people[party][p]], parent[party_people[party][p - 1]]);
        min_num = min(parent[party_people[party][p]], parent[party_people[party][p - 1]]);
        // 각 파티에 참여한 사람을 하나의 그룹으로 만들기
        union_parent(party_people[party][p], party_people[party][p - 1]);
      }
    }

    if(max_num != 0)
    {
      for(int i = 1; i <= N; i++)
      {
        if(parent[i] == max_num)
        {
          parent[i] = min_num;
        }
      }
    }
  }

  vector<bool> result(M + 1, true);
  for(int party = 0; party < M; party++)
  {
    for(int p = 0; p < party_people[party].size(); p++)
    {
      for(int t = 0; t < truth_count; t++)
      {
      	// 각 파티에서 진실을 아는 사람과 같은 그룹에 있다면 과장할 수 없음
        if(parent[party_people[party][p]] == parent[truth_people[t]])
        {
          result[party] = false;
          break;
        }
      }
    }
  }

  int result_count = 0;
  for(int i = 0; i < M; i++)
  {
    // 모두 다르면 결괏값 1 증가
    if(result[i] == true)
    {
      result_count++;
    }
  }

  cout << result_count;

  return 0;
}

// find_parent 연산 : 대표 노드 반환
int find_parent(int a)
{
  if(a == parent[a])
  {
    return parent[a];
  }
  return parent[a] = find_parent(parent[a]);	// 재귀 함수 형태로 구현
}

// union_parent 연산 : 바로 연결이 아닌 대표 노드끼리 연결함
void union_parent(int a, int b)
{
  a = find_parent(a);
  b = find_parent(b);

  if(a < b)
  {
    parent[b] = a;
  }
  else if(b < a)
  {
    parent[a] = b;
  }
}