https://www.acmicpc.net/problem/1043
문제
> 지민이는 파티에 가서 이야기 하는 것을 좋아한다.
> 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다.
> 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다.
> 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다.
> 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다.
> 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다.
> 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다.
> 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다.
> 지민이는 이런 일을 모두 피해야 한다.
> 사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다.
> 그리고 각 파티에 오는 사람들의 번호가 주어진다.
> 지민이는 모든 파티에 참가해야 한다.
> 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.접근
분리집합을 사용하여 Union, Find로 파티원들을 집합화 한다.
먼저 각 사람마다 parent로 꼬리표를 각 번호에 맞게 준다.
이제 피티를 입력받으며 피티구성원의 처음으로 들어온 구성원의 꼬리표와 나머지 파티원을 전부 똑같게 Union하여 집합화 한다.
이제 앞서 진실을 아는 사람으로 받아 저장했던 사람들을 돌며 Find로 꼬리표를 찾아 어떤 집합에 속해있는 상태인지 찾는다.
Find로 재귀를 통해 결국 찾아온 최종 꼬리표에 대해 부울값으로 진실을 안다고 마킹해준다.
이제 다시 모든 파티를 돌며 각각의 구성원에 대해 Find연산을 해서 앞서 마킹해준 부울값과 대조하는데
마킹된 값이면 진실을 아는 사람이 있다는 것이므로 다음 파티로 넘어가고 아니면 거짓말을 해도 되므로 cnt를 누적해 거짓말 가능한 파티의 수를 저장한다.
문제해결
> 분리 집합을 사용하기위해 Find함수와 Union함수를 정의한다.
> Find는 들어온 번호f에 대해 그 번호의 꼬리표와 자기 자신이같으면 그대로 반환하고, 아니면 최종 꼬리표를 찾기위해 어디서 부터 그 꼬리표가 왔는지를 재귀로 탐색해 반환한다.
> Union은 들어온 두 a,b에 대해 두 번호의 Find한 꼬리표가 다르면 다른 집합에 있다는 뜻이므로 이를 하나로 집합화 해준다.
> 꼬리표의 초기값으로 각각의 번호로 초기화해주고 진실을 아는 사람의 번호를 저장해준다.
> 파티의 수 만큼 파티의 구성원들을 i번째 파티에 저장해준다.
> 저장해주며 같은 파티에 속한 구성원들을 한 번호로 집합화 해준다.
> 이제 앞서 저장했던 진실을 아는 사람에 Find를 통해 꼬리표를 근원을 찾고 그 값을 lie 부울 벡터에 마킹해준다.
> 이제 모든 파티를 돌며 각 구성원에 Find로 꼬리표를 찾아 이를 앞서 마킹한 lie에 넣어 비교한다. 파티원중 하나라도 true가 나오면 진실을 아는것이므로 다음파티로 넘어가고
전부 false가 나오면 거짓말을 해도 되므로 rst값을 누적한다.
> 최종 rst값을 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, M;
int K; // 아는 사람
int parent[51];
int Find(int f)
{
if (parent[f] == f) return f;
return parent[f] = Find(parent[f]);
}
void Union(int a, int b)
{
a = Find(a);
b = Find(b);
if (a != b) parent[b] = a;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
for (int i = 1; i <= N; i++) parent[i] = i;
cin >> K;
vector<int> Know(K);
for (int i = 0; i < K; i++) cin >> Know[i];
vector<vector<int>> party(M);
for(int i = 0; i < M; i++)
{
int P;
cin >> P;
party[i].resize(P);
for (int j = 0; j < P; j++) cin >> party[i][j];
for (int j = 1; j < P; j++) Union(party[i][0], party[i][j]);
}
vector<bool> lie(N + 1, false);
for (int i = 0; i < Know.size(); i++)
{
lie[Find(Know[i])] = true;
}
int rst = 0;
for (int i = 0; i < M; i++)
{
bool valid = false;
for (auto a : party[i])
{
if (lie[Find(a)])
{
valid = true;
break;
}
}
if (!valid) rst++;
}
cout << rst << '\n';
}
후기
아직 분리집합이 익숙치 않아 어려웠고 꼬리표 따라가는게 헷갈렸다.
더 많이 풀어보자
