이 문제는 확장된 범위의 유니온-파인드(Union-Find) 데이터 구조를 활용한 알고리즘 문제입니다. 일반적인 유니온-파인드는 요소 간 연결 관계를 표현하지만, 이 문제에서는 추가적인 속성(친구/적 등)을 고려해야 합니다.
확장된 범위 유니온-파인드는 복수의 속성을 다루기 위해 여러 영역(domain)을 생성합니다. 예를 들어, 인물 x의 친구 관계는 x, 적은 x+n으로 매핑하며, 이는 서로 다른 영역에서 관계를 관리하는 방식입니다. 두 관계 사이의 상호작용을 반영하려면 각 관계에 대해 양방향으로 연결을 처리해야 합니다.
다음은 문제 해결을 위한 코드 예시입니다:
#include <iostream>
#include <vector>
using namespace std;
const int MAX_SIZE = 30010;
int parent[MAX_SIZE];
int num_people, num_enemies, rel_cnt, query_cnt;
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> num_people >> num_enemies >> rel_cnt >> query_cnt;
// 초기화: 사람과 적 모두 자기 자신으로 설정
for (int i = 1; i <= num_people + num_enemies; ++i) {
parent[i] = i;
}
// 관계 정보 처리
while (rel_cnt--) {
int a, b;
cin >> a >> b;
if (find(a) != find(b)) {
parent[find(a)] = find(b);
}
}
// 질의 처리
while (query_cnt--) {
int x, y;
cin >> x >> y;
// 적 관계로 매핑
if (find(x + num_people) != find(y + num_people)) {
parent[find(x + num_people)] = find(y + num_people);
}
}
// 결과 계산
int group1 = 0, group2 = 0;
for (int i = 1; i <= num_people; ++i) {
if (find(i) == find(1)) group1++;
}
for (int i = num_people + 1; i <= num_people + num_enemies; ++i) {
if (find(i) == find(num_people + 1)) group2++;
}
cout << min(group1, group2) << endl;
return 0;
}
두 번째 변형 예시:
#include <iostream>
#include <array>
using namespace std;
const int MAX_ELEMENTS = 30010;
array parent;
int person_count, enemy_count, relation_num, query_num;
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> person_count >> enemy_count >> relation_num >> query_num;
// 초기화: 모든 요소가 자기 자신으로 설정
for (int i = 1; i <= person_count + enemy_count; ++i) {
parent[i] = i;
}
// 관계 처리
while (relation_num--) {
int u, v;
cin >> u >> v;
if (find(u) != find(v)) {
parent[find(u)] = find(v);
}
}
// 질의 처리
while (query_num--) {
int a, b;
cin >> a >> b;
// 적 관계로 매핑 후 처리
if (find(a + person_count) != find(b + person_count)) {
parent[find(a + person_count)] = find(b + person_count);
}
}
// 그룹 수 계산
int groupA = 0, groupB = 0;
for (int i = 1; i <= person_count; ++i) {
if (find(i) == find(1)) groupA++;
}
for (int i = person_count + 1; i <= person_count + enemy_count; ++i) {
if (find(i) == find(person_count + 1)) groupB++;
}
cout << min(groupA, groupB) << endl;
return 0;
}