링크
https://www.acmicpc.net/problem/1043
문제 설명
정답률 45.078%
지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.
사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다. 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.
입력 예제
- 첫째 줄에 사람의 수 N과 파티의 수 M이 주어진다.
- 둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다. 사람들의 번호는 1부터 N까지의 수로 주어진다.
- 셋째 줄부터 M개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.
- N, M은 50 이하의 자연수이고, 진실을 아는 사람의 수는 0 이상 50 이하의 정수, 각 파티마다 오는 사람의 수는 1 이상 50 이하의 정수이다.
5 4
1 5
2 1 2
2 2 3
2 3 4
2 4 5
출력 예제
- 첫째 줄에 문제의 정답을 출력한다.
0
풀이
진실을 아는 사람이 주어지고 이 사람이 포함된 파티에서는 진실을 말할 수 없다. 이 말은 결국 진실을 아는 사람이 아닐 지라도 그 파티에 포함만 돼있으면 간접적으로 진실 여부를 아는 사람이 된다.
각 파티 참가자들 중 진실을 아는 사람이 포함된 사람이 있는지 탐색하고 포함이 돼있으면 나머지 참가자들도 진실을 아는 사람으로 판단한다.
단, 탐색을 할 때 특정 파티에 이미 진실을 아는 사람이 없다고 판단을 했는데 다른 파티에서 판단한 결과 나중에 진실을 알게 된 사람이 존재할 수 있으므로 탐색은 파티의 수만큼 반복한다.
코드
//백준
public class Main {
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); //사람의 수
int M = Integer.parseInt(st.nextToken()); //파티의 수
st = new StringTokenizer(br.readLine());
int knownCount = Integer.parseInt(st.nextToken()); //진실을 아는 사람 수
boolean[] knownPeople = new boolean[N + 1]; //진실을 아는 사람들의 번호
//진실을 아는 사람이 있을 때
if (knownCount > 0) {
//입력값 세팅
for (int i = 0; i < knownCount; i++) {
int num = Integer.parseInt(st.nextToken());
knownPeople[num] = true;
}
}
//파티 리스트
List<int[]> totalParty = new ArrayList<>();
//입력값 세팅
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int party = Integer.parseInt(st.nextToken()); //파티의 사람 수
int[] partyPeople = new int[party]; //파티에 온 사람들의 번호
for (int j = 0; j < party; j++) {
partyPeople[j] = Integer.parseInt(st.nextToken());
}
totalParty.add(partyPeople);
}
//파티 수 만큼 반복
for (int i = 0; i < M; i++) {
//각 파티에 진실을 아는 사람이 포함되는지 탐색
//포함되면 나머지 파티원들도 알게 된다.
for (int[] party : totalParty) {
isContained(party, knownPeople);
}
}
int count = 0;
//진실을 아는 사람이 있는 파티를 카운트
for (int[] party : totalParty) {
for (int participant : party) {
if (knownPeople[participant]) {
count++;
break;
}
}
}
System.out.println(M - count);
}
static void isContained(int[] party, boolean[] knownPeople) {
for (int i = 0; i < party.length; i++) {
int num = party[i];
//파티에 아는 사람이 있으면
if (knownPeople[num]) {
//나머지 사람들도 알게 됨
for (int n : party) {
knownPeople[n] = true;
}
}
}
}
}정리
처음에는 이게 왜 골드인지 모르겠을 정도로 입력값을 세팅하는게 오히려 더 힘들었는데 반례를 찾아보니 나중에 진실을 알게된 사람이 있을 수 있고 파티의 순서가 없기 때문에 탐색을 파티의 수 만큼 반복해줬어야 했다.
하지만 이것은 단순히 반복을 하여 푼 것이었고 이 문제는 분리 집합(Disjoint Set) 알고리즘으로 분류되어 있어서 Union-Find로 공부할 겸 풀이해보았다.
Union-Find는 각 연결된 노드를 하나의 집합으로 하여 부모 노드를 찾는 것이다. 각 집합의 부모 노드의 동일 여부를 판단하여 서로 다른 노드의 같은 집합 여부를 판단할 수 있다.
보통 더 작은 노드를 기준으로 부모 노드를 정하지만 이 문제는 진실을 아는 사람을 부모 노드로 하여 집합을 구분하여야 한다. 그래서 각 파티 참가자들을 합칠 때 진실을 아는 사람이 포함되어 있는지를 기준으로 부모 노드를 설정한다.
입력 예제를 기준으로 각 노드를 표현해보면 다음과 같다. 부모 노드는 5가 되며 모든 노드가 같은 집합인 것을 확인할 수 있다.
코드
//백준
public class Main {
static int[] parents;
static List<Integer> knownPeople;
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); //사람의 수
int M = Integer.parseInt(st.nextToken()); //파티의 수
//부모 노드 초기화
parents = new int[N + 1];
for (int i = 0; i <= N; i++) {
parents[i] = i;
}
st = new StringTokenizer(br.readLine());
int knownCount = Integer.parseInt(st.nextToken()); //진실을 아는 사람 수
knownPeople = new ArrayList<>(); //진실을 아는 사람 번호 리스트
if (knownCount == 0) {
System.out.println(M);
return;
} else {
for (int i = 0; i < knownCount; i++) {
knownPeople.add(Integer.parseInt(st.nextToken()));
}
}
List<int[]> parties = new ArrayList<>();
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int peopleCount = Integer.parseInt(st.nextToken()); //각 파티의 사람 수
int[] party = new int[peopleCount]; //각 파티 배열
int x = Integer.parseInt(st.nextToken()); //첫번째 사람
party[0] = x;
//첫번째 사람과 나머지 사람을 합침
for (int j = 1; j < peopleCount; j++) {
int y = Integer.parseInt(st.nextToken());
unionParent(x, y);
party[j] = y;
}
parties.add(party);
}
int count = 0;
for (int[] party : parties) {
for (int i : party) {
int findParent = getParent(parents[i]);
//파티 참가자의 부모 노드가 리스트에 포함될 때 카운트
if (knownPeople.contains(findParent)) {
count++;
break;
}
}
}
System.out.println(M - count);
}
//부모 노드를 찾는 메서드
static int getParent(int x) {
if (parents[x] == x) {
return x;
}
return getParent(parents[x]);
}
//두 부모 노드를 합치는 메서드
static void unionParent(int a, int b) {
a = getParent(a);
b = getParent(b);
//진실을 아는 사람을 부모 노드로 하여 합친다.
if (knownPeople.contains(b)) {
parents[a] = b;
} else {
parents[b] = a;
}
}
}참고
