문제
지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.
사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다. 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 사람의 수 N과 파티의 수 M이 주어진다.
둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다. 사람들의 번호는 1부터 N까지의 수로 주어진다.
셋째 줄부터 M개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.
N, M은 50 이하의 자연수이고, 진실을 아는 사람의 수는 0 이상 50 이하의 정수, 각 파티마다 오는 사람의 수는 1 이상 50 이하의 정수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
풀이
이 문제는 파티마다 사람들을 연결해 놓고, 그 연결 요소 안에 진실을 아는 사람이 한 명이라도 섞여 있는지만 보면 된다. 한 번 같은 파티에 들어간 사람들은 이후 다른 파티를 통해서도 진실 여부가 전파될 수 있으므로, 파티 단위로 사람들을 계속 묶어야 한다.
코드에서는 union-find를 사용하고, 진실을 아는 사람들을 가상의 루트 0과 union 해서 하나의 특별한 집합으로 만든다. 이후 각 파티의 참가자들을 모두 같은 집합으로 묶으면, 결국 0과 연결된 집합은 진실을 알아서 거짓말을 할 수 없는 그룹이 된다.
모든 파티를 읽은 뒤 각 파티의 대표 사람 하나를 꺼내 find(대표) != find(0)인지 확인하면 된다. 0과 연결되지 않은 파티만 과장된 이야기를 할 수 있으므로, 그런 파티의 개수를 세면 정답이다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[] parent;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
parent = new int[N + 1];
for (int i = 0; i <= N; i++) {
parent[i] = i;
}
st = new StringTokenizer(br.readLine());
int trueCount = Integer.parseInt(st.nextToken());
// 진실 알면 모두 0(최상위)으로
for (int i = 0; i < trueCount; i++) {
int truePerson = Integer.parseInt(st.nextToken());
union(0, truePerson);
}
int ans = solve();
System.out.println(ans);
}
public static int solve() throws IOException {
StringTokenizer st;
ArrayList<Integer>[] parties = new ArrayList[M];
for (int i = 0; i < M; i++) {
parties[i] = new ArrayList<>();
st = new StringTokenizer(br.readLine());
int partySize = Integer.parseInt(st.nextToken());
int firstPerson = Integer.parseInt(st.nextToken());
parties[i].add(firstPerson);
// 파티원끼리 묶기
for (int j = 1; j < partySize; j++) {
int nextPerson = Integer.parseInt(st.nextToken());
parties[i].add(nextPerson);
union(firstPerson, nextPerson);
}
}
int ans = 0;
for (int i = 0; i < M; i++) {
int partyLeader = parties[i].get(0);
// 0이 아니면 거짓말 가능
if (find(partyLeader) != find(0)) {
ans++;
}
}
return ans;
}
public static int find(int x) {
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
public static void union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
if (a < b) parent[b] = a;
else parent[a] = b;
}
}
}복잡도
- 시간 복잡도: 전체 파티 참가 기록 수를 라 하면 union-find 연산으로 이다.
- 공간 복잡도: 부모 배열과 파티 정보를 저장하므로 이다.
마무리
처음에는 파티를 여러 번 전염시키는 시뮬레이션처럼 보이지만, 결국 같은 파티에 나온 사람들을 하나의 집합으로 묶는 문제다. 진실 집합을 루트 0으로 두면 판정도 아주 단순해진다.
