[백준] 1043번 - 거짓말 (Gold 4)
업데이트:
문제 링크
문제 설명
파티에서 다음 두 가지 조건을 만족하면서 거짓말을 최대한 많이 하고자 한다.
- 한 명이 어떤 파티에서는 진실을, 어떤 파티에서는 거짓말을 듣는 경우는 없어야 한다.
- 처음부터 진실을 알고 있던 사람이 있는 파티에서 거짓말을 해서도 안된다.
이 때, 거짓말을 할 수 있는 최대 횟수를 구하면 된다.
정답 코드 및 설명
처음부터 진실을 알고 있던 사람들로 시작해서, 같은 파티에 참석하는 사람들은 모두 진실을 들어야 한다.
이를 구현하기 위해 파티의 참가자 목록과 사람들이 참가한 파티 목록을 둘 다 저장하였다.
처음부터 진실을 알고 있던 사람들이 참가한 파티들로 시작해서 BFS를 수행한다.
같은 파티에 있는 사람들을 모두 연결된 것으로 취급하면 된다.
파티나 사람은 한번만 체크하면 충분하므로, 각각을 체크하기 위한 변수도 사용한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
Party party = new Party(n, m);
// 진실을 알고 있는 사람의 목록 = personTrue
st = new StringTokenizer(br.readLine());
int numTrue = Integer.parseInt(st.nextToken());
int[] personTrue = new int[numTrue];
for (int i = 0; i < numTrue; i++)
personTrue[i] = Integer.parseInt(st.nextToken()) - 1;
// partyList[], party[] 만들기
for (int i = 0; i < m; i++) {
party.party[i] = new ArrayList<>();
st = new StringTokenizer(br.readLine());
int partyPeople = Integer.parseInt(st.nextToken());
for (int j = 0; j < partyPeople; j++) {
int person = Integer.parseInt(st.nextToken()) - 1;
party.partyList[person].add(i);
party.party[i].add(person);
}
}
bw.write(max(personTrue, party) + "");
bw.close();
}
static int max(int[] personTrue, Party party) {
int max = party.m;
boolean[] checkPerson = new boolean[party.n]; // 사람 체크
boolean[] checkParty = new boolean[party.m]; // 파티 체크
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < personTrue.length; i++) {
queue.add(personTrue[i]);
checkPerson[personTrue[i]] = true;
}
while (!queue.isEmpty()) {
int curr = queue.poll();
// 진실을 알게 된 사람이 참가한 파티 목록
Iterator<Integer> iter = party.partyList[curr].iterator();
while (iter.hasNext()) {
int partyIndex = iter.next();
// 이미 체크한 파티면 스킵
if (checkParty[partyIndex])
continue;
checkParty[partyIndex] = true;
max--; // 거짓을 말할 수 없는 파티이므로 max 1 감소
// 파티에 같이 참가한 사람들 체크
Iterator<Integer> iter2 = party.party[partyIndex].iterator();
while (iter2.hasNext()) {
int person = iter2.next();
if (checkPerson[person])
continue;
checkPerson[person] = true;
queue.add(person);
}
}
}
return max;
}
}
class Party {
ArrayList<Integer> partyList[], party[];
int n, m;
Party(int n, int m) {
partyList = new ArrayList[n];
for (int i = 0; i < n; i++)
partyList[i] = new ArrayList<>();
party = new ArrayList[m];
for (int i = 0; i < m; i++)
party[i] = new ArrayList<>();
this.n = n;
this.m = m;
}
}
나중에 찾아본 결과, 이 문제는 분리 집합 문제로, Union-Find라는 알고리즘으로 푼다고 한다.
현재는 이 쪽에 대해서는 아는게 아예 없으니, 추후에 공부해서 다시 풀어봐야겠다.
댓글남기기