[백준]1042: 거짓말 - JAVA
[백준]1042: 거짓말
https://www.acmicpc.net/problem/1043
1043번: 거짓말
지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게
www.acmicpc.net
풀이
🪑 문제를 따라 조건들을 차례차례 정리해 보았다.
- 지민 -> 진실 OR 과장(되도록 과장 BUT 거짓말 들키기 싫어함)
- 진실 아는 사람 존재 -> 과장 할 수 없음.
- 진실을 한 번 이라도 들은 사람은 진실을 아는 사람이다.
🔧 위의 조건들을 토대로 어떻게 풀지 풀이 순서를 적어보았다.
- 진실을 아는 사람들의 정보를 모은다.
- 진실을 아는 사람이 속해있는 파티를 조사하여 해당 파티원들을 전부 진실을 아는 사람들의 정보에 추가한다.
- 이미 진실을 아는 사람이거나, 이미 확인한 파티는 조사하지 않는다.
위의 방식대로 하나씩 구현해 나가 보자!
🔹 진실을 아는 사람들의 정보를 모은다.
- 진실을 아는 사람들의 정보를 입력 받을때면서 리스트에 저장해 주었다.
🔹 진실을 아는 사람이 속해있는 파티를 조사하여 해당 파티원들을 진실을 아는 사람들의 정보에 추가한다.
- BFS 탐색을 사용하였다. 해당 코드는를 구현하고 보니 위상정렬 코드와 유사하게 구현하였다.
- 먼저, 큐에 진실을 아는 사람들의 정보를 담아주고 한명 한명씩 속해있는 파티를 조사해 준다.
- 조사할 때는 조사하지 않은 파티 중에서, 현재 사람이 속해있는 파티를 조사해 주었다.
- 만약 이미 진실을 알고 있는 사람을 발견하면 다시 그 사람을 확인하지 않아도 되므로 진실을 모르는 사람들의 정보를 큐에 담아주었다.
- 현재 사람이 속해있는 파티가 존재했다면 해당 파티는 더 이상 과장되서 말할 수 없는 파티가 되므로 현재까지 과장되어 말할 수 있는 파티의 개수에서 1을 줄여준다.
🔹이미 진실을 아는 사람이거나, 이미 확인한 파티는 조사하지 않는다.
- 파티 방문 여부를 체크하는 Boolean배열과, 이미 진실을 알고 있는 사람 여부를 체크하는 Boolean배열을 사용해 주었다.
코드
|
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
|
import java.util.*;
public class Main {
static ArrayList<Integer> truth = new ArrayList<>();
static ArrayList<Integer>[] party;
static int n, m;
static int total_party;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
int t = scan.nextInt();
for(int i = 0; i < t; i++) {
truth.add(scan.nextInt());
}
party = new ArrayList[m];
for(int i = 0; i < m; i++) {
party[i] = new ArrayList<>();
int num = scan.nextInt();
for(int j = 0; j < num; j++) {
party[i].add(scan.nextInt());
}
}
total_party = m;
find_truth();
System.out.println(total_party);
}
public static void find_truth() {
Queue<Integer> q = new LinkedList<>();
boolean[] party_visited = new boolean[m];
boolean[] people_visited = new boolean[n + 1];
for(int i = 0; i < truth.size(); i++) {
q.offer(truth.get(i));
people_visited[truth.get(i)] = true;
}
while(!q.isEmpty()) {
int current = q.poll();
for(int i = 0; i < m; i++) {
if(!party_visited[i] && party[i].contains(Integer.valueOf(current))) {
for(int j = 0; j < party[i].size(); j++) {
int next = party[i].get(j);
if(!people_visited[next]) {
people_visited[next] = true;
q.offer(next);
}
}
total_party--;
party_visited[i] = true;
}
}
}
}
}
|
cs |