[1043] 거짓말

문제 링크 : https://www.acmicpc.net/problem/1043

1043 - 거짓말

본문

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.

사람의 수 $N$이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다. 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 $N$과 파티의 수 $M$이 주어진다.

둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다. 사람들의 번호는 $1$부터 $N$까지의 수로 주어진다.

셋째 줄부터 $M$개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.

$N, M$은 $50$ 이하의 자연수이고, 진실을 아는 사람의 수는 $0$ 이상 $50$ 이하의 정수, 각 파티마다 오는 사람의 수는 $1$ 이상 $50$ 이하의 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

제한

시간 제한	메모리 제한
2sec	128MB

---

풀이

사람들을 2가지로 아예 나눠버릴 수 있다. ‘진실을 알거나 알게 되는 사람’과 ‘진실을 끝까지 모르는 사람’. 진실을 끝까지 모르는 사람들이 있는 파티에서만 과장된 이야기를 할 수 있을 것이다. 진실을 아는 사람이 있다면 과장된 얘기를 할 수 없다. 그리고, 진실을 알게 될 사람들이 있어도 과장된 이야기를 할 수 없다. 그러므로, 진실을 알고 있거나 알게 될 사람을 모두 찾아내야한다.

찾아내는 것은 어렵지 않다. 파티에 속하는 사람들은 서로 모두 이어지는 그래프가 있다고 생각하면 된다. 그리고 진실을 아는 사람과 하나라도 연결되어있다면 그 사람은 곧 진실을 알게 될 사람이라는 것이다. 하나의 파티는 하나의 그룹으로 묶여서 공동체를 이루게 된다.

그리고 그 그룹은, 다른 그룹과도 연결될 수 있다. 마치 유니온파인드를 보는 것 같다. 굳이 그래프를 그려서 탐색하지 말고, 파티에 어떤 사람들이 참석했는가만 따로 기록하는 방법으로 유니온파인드를 활용할 수 있다. 서로 연결되는 사람들까지 그룹으로 전부 묶어두자.

그룹으로 묶은 다음, 진실이 어디까지 전파될 수 있는지 확인한다. 이미 진실을 아는 사람들이 속한 그룹 전체가 그 대상이 될 것이다.

진실이 모두 퍼진 이후, 우리는 과장된 이야기를 할 수 있는 파티를 찾을 수 있을 것이다. 파티에 참석하는 모든 사람들에 대해, 모두가 진실을 알지 못한다면 과장된 이야기를 할 수 있다. 즉, 사람들이 속한 그룹이 진실을 아는 사람이 있는지 확인하면 된다. 당연하게도, parent만 확인하면 빠르게 알아낼 수 있다.

• 참고 알고리즘 : 분리 집합

코드

사용 언어 : C

최종 수정일 : 2023 / 4 / 18

#include <stdio.h>

typedef char bool;
const bool true = 1;
const bool false = 0;

#define MAX_IDX (50 + 1)
int truth[MAX_IDX];
bool isTruth[MAX_IDX];
int n, m, truth_len;

int parent[MAX_IDX];
int find(int x) {
    if (x == parent[x]) {
        return x;
    } else {
        return parent[x] = find(parent[x]);
    }
}
void merge(int a, int b) {
    int x = find(a), y = find(b);

    if (x != y) {
        parent[y] = parent[b] = x;
    }
    return;
}

int party[MAX_IDX][MAX_IDX];

void read_input() {
    for (int i = 0; i < truth_len; ++i) {
        scanf("%d", truth + i);
    }
    for (int i = 0; i < m; ++i) {
        scanf("%d", &party[i][0]);
        for (int j = 1; j <= party[i][0]; ++j) {
            scanf("%d", &party[i][j]);
            merge(party[i][1], party[i][j]);
        }
    }
    return;
}
void disjoint_init() {
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
    }
    return;
}

bool truthNotExists(int x) {
    bool retval = false;
    for (int i = 1; i <= party[x][0]; ++i) {
        retval |= isTruth[find(party[x][i])];
    }
    return (retval == false);
}

int main() {
    scanf("%d %d %d", &n, &m, &truth_len);
    disjoint_init();
    read_input();

    for (int i = 0; i < truth_len; ++i) {
        isTruth[truth[i]] = isTruth[find(truth[i])] = true;
    }

    int result = 0;
    for (int i = 0; i < m; ++i) {
        result += truthNotExists(i);
    }

    printf("%d", result);
    return 0;
}