문제
지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.
사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다. 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.
문제를 요약하자면 이렇습니다.
1.
M개의 파티가 주어졌을 때 거짓말을 할 수 있는 최댓값
2.
파티에 단 한 명이라도 진실을 알고 있는 자가 있다면 PASS
3.
진실을 알고 있는 자가 포함된 파티의 파티원들은 다 진실을 알게 됨
입력
첫째 줄에 사람의 수 N과 파티의 수 M이 주어진다.
둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다. 사람들의 번호는 1부터 N까지의 수로 주어진다.
셋째 줄부터 M개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.
입력 예제가 다음과 같다면
10 9 // 사람은 10명, 파티 수는 9개
4 1 2 3 4 // 진실을 알고 있는 자는 1, 2, 3, 4
2 1 5
2 2 6
1 7
1 8
2 7 8
1 9
1 10
2 3 10
1 4
Java
복사
문제에 대한 접근
ArrayList를 중복으로 사용해 파티에 대한 파티원들을 저장하였습니다.
예를 들어 위의 입력에서 파티는 총 다섯 개 이므로 다섯개의 ArrayList를 생성하였습니다.
또한, 해당 파티에 참여한 인원들을 ArrayList의 형태로 나타냈습니다.
party = new ArrayList<>();
for (int i = 0; i < M; i++) {
party.add(new ArrayList<>());
}
// 파티 정보를 ArrayList에 저
for (int i = 0; i < M; i++) {
s = br.readLine().split(" ");
for (int j = 0; j < s.length; j++) {
party.get(i).add(Integer.parseInt(s[j]));
}
}
Java
복사
그 다음에는 진실을 알고 있는 자가 한 명이라도 속한 파티가 있다면 파티원 모두를 진실을 알고 있는자로 매핑하는 과정을 거쳤습니다. 이 때는 Union - Find 알고리즘을 사용했습니다.
예를 들어, 3번, 4번, 8번, 9번이 속한 파티가 있다고 가정해봅시다. 그리고 이 때 3번은 진실을 알고 있는 사람이 됩니다. 그러면 4번, 8번, 9번 또한 진실을 알고 있는 자로 바뀌게 됩니다.
boolean [] truth 을 만들고 진실을 알고 있는 인원을 True로 아닌 인원을 False로 만들어도 되지만, 저는 다음과 같이 구별하고자 하였습니다.
Union - Find 함수에서 사용되는 Parent [] 배열의 일부분입니다. 만약 3번이 진실을 알고 있는 자였다면, 나머지 인원들을 모두 3을 가르키게 됩니다.
truth [] = {false, false, false, true … }
for (int j = 0; j < P; j++) {
if (truth[parent[party.get(i).get(j + 1)]]) {
isAble = true;
break;
}
}
if (!isAble)
cnt++;
Java
복사
후에 해당 파티에 진실을 알고 있는자가 있는지 확인할 때, parent[] 의 값을 조회하여서 판별할 수 있습니다.
코드
package baekjoon.data_structure;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class _1043 {
public static int[] parent;
public static boolean[] truth;
public static ArrayList<ArrayList<Integer>> party;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
// 사람 N, 파티의 수 M
int N = Integer.parseInt(s[0]);
int M = Integer.parseInt(s[1]);
// 진실을 알고 있는 사람을 판별하기 위한 배열
truth = new boolean[N + 1];
parent = new int[N + 1];
// parent 함수 Initialization
for (int i = 1; i < parent.length; i++) {
parent[i] = i;
}
party = new ArrayList<>();
// 진실을 알고 있는 수를 입력 받음
s = br.readLine().split(" ");
int T = Integer.parseInt(s[0]);
// 만약 0이 아니라면
if (T != 0) {
for (int i = 0; i < T; i++) {
truth[Integer.parseInt(s[i + 1])] = true;
}
}
for (int i = 0; i < M; i++) {
party.add(new ArrayList<>());
}
// 파티 정보를 ArrayList에 저장
for (int i = 0; i < M; i++) {
s = br.readLine().split(" ");
for (int j = 0; j < s.length; j++) {
party.get(i).add(Integer.parseInt(s[j]));
}
}
for (int k = 0; k < M; k++) {
for (int i = 0; i < M; i++) {
int P = party.get(i).get(0);
boolean isTruth = false;
int temp = 0;
for (int j = 0; j < P; j++) {
if (truth[parent[party.get(i).get(j + 1)]]) {
isTruth = true;
temp = party.get(i).get(j + 1);
break;
}
}
if (isTruth) {
for (int j = 0; j < P; j++) {
union(temp, party.get(i).get(j + 1));
}
}
}
}
int cnt = 0;
for (int i = 0; i < M; i++) {
int P = party.get(i).get(0);
boolean isAble = false;
for (int j = 0; j < P; j++) {
if (truth[parent[party.get(i).get(j + 1)]]) {
isAble = true;
break;
}
}
if (!isAble)
cnt++;
}
System.out.println(cnt);
}
public static int find(int x) {
if (x == parent[x]) return x;
return parent[x] = find(parent[x]);
}
public static void union(int x, int y) {
x = find(x);
y = find(y);
if (truth[x])
parent[y] = x;
else parent[x] = y;
}
}
Java
복사
