이번 문제는 백준의 골드4 문제 거짓말 문제이다.
문제를 차근차근 읽어보도록 하자.
지민이는 얘기를 과장되게 하는 거짓말쟁이이다.
지민이가 파티에 참석을 할 것인데, 거짓말쟁이로 소문이 나서는 안된다.
그러기 위해서는 진실을 아는 사람과 같은 파티에 가서는 안된다.
또한, 진실을 들은 사람이 있는 파티에도 참석할 수 없다.
최대 50명의 사람이 주어지며, 50개의 파티가 주어질 수 있다.
또한, 진실을 아는 사람이 주어진다.
문제를 어떻게 풀어야 할까?
완전 탐색?
가장 먼저 떠오르는 풀이는 모든 파티를 훑어보는 완전탐색이다.
진실을 아는 사람들을 1차원 배열에 boolean 값으로 저장을 한다.
이후 주어지는 파티에 입력되는 모두에 대해 진실을 아는 사람이 있는지 확인한다.
만약 진실을 아는 사람이 한 명이라도 있는 파티라면, 지민이는 진실을 말해야 한다.
이 때 관건은 진실을 아는 사람이 있는 파티에 있던 모두도 진실을 알게 된다는 점이다.
그럼 파티에 있던 모두를 boolean 값으로 다시 표시해주어야 한다는 말이다.
만약 배열을 훑는 중, 진실을 아는 사람이 중간에 끼어있다면 처음부터 배열을 다시 돌아야 한다.
그래서 아래와 같이 참여할 수 없는 파티를 따로 저장해주었다.
for (int i = 1; i <= parties; i++) {
cin >> party_members;
bool is_known = false;
for (int j = 0; j < party_members; j++) {
cin >> person;
graph[i].push_back(person);
if (know[person] && !is_known) {
dangerous_party.push_back(i);
dangerous_check[i] = true;
is_known = true;
}
}
} // O(N^2) => 최대 2500이후, dangerous_party를 따로 한번더 돌면서 진실을 아는 사람을 체크했다.
마지막으로 파티 전체를 한번 더 순회하며, 진실을 아는 사람이 있는 파티를 제외시켰다.
int answer = parties;
answer -= dangerous_party.size(); // 여긴 어차피 못감
for (int i = 1; i <= parties; i++) {
if (!dangerous_check[i]) {
for (int j = 0; j < graph[i].size(); j++) {
if (know[graph[i][j]]) {
answer--;
break;
}
}
}
}테스트 케이스에서는 모두 정답을 받을 수 있었지만, 반례를 발견했다.
예를 들어 1 2 / 2 3 / 3 4 / 4 5와 같이 순차적으로 파티가 열리는 경우
만약 5번 사람이 진실을 알고 있는 사람이라면?
내가 구현한 방식대로 순회하면 3 4 / 4 5를 제외하곤 모두 참여할 수 있는 것이다.
하지만 지민이는 실제론 모든 파티에 참여할 수 없다.
Union find?
관건은 진실을 아는 사람이 있는 파티의 모든 참여자를 어떻게 기록할 것인가이다.
위에서 언급했던 반례를 해결하려면, 그래프 탐색을 해야할 것 같다는 생각이 든다.
고민을 하다보니, 집합을 표현할 수 있는 Union Find가 문득 떠올랐다.
모든 같은 파티에 참여하는 사람들을 동일한 부모 노드로 묶어 집합으로 만든다.
이후 계속 새로 들어오는 파티 입력에 대해서도 하나의 집합으로 만들어 낸다.
마지막으로 파티를 하나씩 돌며, 참가한 사람들이 진실을 아는 사람들과 같은 집합인지 검사한다.
같은 집합인 사람이 한 명이라도 있으면 바로 해당 파티는 못가도록 처리한다.
먼저, 파티는 원래대로 인접 행렬의 형태로 저장하도록 했다.
이후 인접 행렬을 순회하며, 같은 파티의 사람들을 같은 집합으로 묶는다.
for (int i = 1; i <= parties; i++)
for (int j = 1; j < graph[i].size(); j++)
do_union(graph[i][0], graph[i][j]);
// 여기서 각 파티별로 사람을 묶는다.마지막으로 파티 전체를 순회하며 각 파티의 조합을 확인한다.
한 사람씩 확인하며 진실을 아는 사람과 같은 집합인 사람이 있는지 확인한다.
만약 어떤 사람이 진실을 아는 사람과 같은 집합에 속했다면?
현재 파티가 아니더라도, 다른 파티에서 만난다는 말이다.
결국 해당 파티는 지민이가 가서는 안되는 파티인 것이 된다!
for (int i = 1; i <= parties; i++) {
// 파티 전체를 돌며 갈 수 있는지 확인한다.
bool can_go = true;
for (int j = 0; j < graph[i].size(); j++) {
if (!can_go)
break;
int participant = graph[i][j];
for (int k = 0; k < know.size(); k++) {
int knower = know[k];
if (check_parent(participant, knower)) {
can_go = false;
break;
}
}
}
if (!can_go)
answer--;
}최종적으로 아래와 같이 구현했다.
int find_parent(int node) {
if (mst[node] == node)
return node;
return mst[node] = find_parent(mst[node]);
}
void do_union(int node_x, int node_y) {
node_x = find_parent(node_x);
node_y = find_parent(node_y);
mst[node_y] = node_x;
}
void init_mst() {
for (int i = 1; i <= num; i++)
mst[i] = i;
}
bool check_parent(int node_x, int node_y) {
node_x = find_parent(node_x);
node_y = find_parent(node_y);
if (node_x == node_y)
return true;
return false;
}
int main() {
OPTIMIZE;
cin >> num >> parties;
cin >> knowers;
for (int i = 0; i < knowers; i++) {
cin >> person;
know.push_back(person);
}
for (int i = 1; i <= parties; i++) {
cin >> party_members;
for (int j = 0; j < party_members; j++) {
cin >> person;
graph[i].push_back(person);
}
}
init_mst();
int answer = parties; // 원래 파티 수로 초기화
for (int i = 1; i <= parties; i++)
for (int j = 1; j < graph[i].size(); j++)
do_union(graph[i][0], graph[i][j]);
// 여기서 각 파티별로 사람을 묶는다.
for (int i = 1; i <= parties; i++) {
// 파티 전체를 돌며 갈 수 있는지 확인한다.
bool can_go = true;
for (int j = 0; j < graph[i].size(); j++) {
if (!can_go)
break;
int participant = graph[i][j];
for (int k = 0; k < know.size(); k++) {
int knower = know[k];
if (check_parent(participant, knower)) {
can_go = false;
break;
}
}
}
if (!can_go)
answer--;
}
cout << answer;
return 0;
}