728x90
백준 1043 - 거짓말
https://www.acmicpc.net/problem/1043

문제
파티에서 이야기를 말할 때, 있는 그대로 말하거나 과장해서 말함
거짓말쟁이로 알려지기 싫기 때문에 진실을 아는 사람이 파티에 오면 진실을 이야기 함
어떤 사람이 파티에서 진실을 듣고, 또 다른 파티에서 과장된 이야기를 들으면 거짓말쟁이로 알려짐
입력
첫째 줄: 사람 수 N, 파티 수 M (1 <= N, M <= 50)
둘째 줄: 이야기의 진실 아는 사람 수와 번호 (0 <= 진실 아는 사람 수 <= 50)
(진실을 아는 사람 수 먼저 주어지고 그 개수만큼 사람들 번호(1 ~ N) 주어짐)
셋째 줄 ~ M개 줄: 각 파티마다 오는 사람 수, 번호 (1 <= 각 파티마다 오는 사람 수 <= 50)
출력: 거짓말쟁이로 알려지지 않으면서 과장된 이야기를 할 수 있는 파티 개수의 최댓값
풀이
Union-Find (같은 파티 참석 -> 같은 그룹)
for (int i = 0; i < M; i++) {
int cnt = Integer.parseInt(st.nextToken()); // 파티 참가자 수
List<Integer> party = new ArrayList<>();
for (int j = 0; j < cnt; j++) {
party.add(Integer.parseInt(st.nextToken()));
}
parties.add(party);
// 파티의 모든 사람을 하나의 그룹으로 묶기
for (int j = 0; j < cnt - 1; j++) {
union(party.get(j), party.get(j + 1));
}
}
진실을 아는 사람 루트 저장
Set<Integer> truthRoots = new HashSet<>();
for (int x : truthPeople) {
truthRoots.add(find(x));
}
코드
import java.io.*;
import java.util.*;
// 거짓말
public class boj_1043 {
static int N, M;
static int[] unf;
static List<Integer> truthPeople;
static List<List<Integer>> parties;
static int find(int v) {
if (v == unf[v]) return v;
return unf[v] = find(unf[v]);
}
static void union(int a, int b) {
int fa = find(a);
int fb = find(b);
if (fa != fb) unf[fb] = fa;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
unf = new int[N + 1];
for (int i = 1; i <= N; i++) unf[i] = i;
st = new StringTokenizer(br.readLine());
int t = Integer.parseInt(st.nextToken());
truthPeople = new ArrayList<>();
for (int i = 0; i < t; i++) {
truthPeople.add(Integer.parseInt(st.nextToken()));
}
parties = new ArrayList<>();
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int cnt = Integer.parseInt(st.nextToken());
List<Integer> party = new ArrayList<>();
for (int j = 0; j < cnt; j++) {
party.add(Integer.parseInt(st.nextToken()));
}
parties.add(party);
for (int j = 0; j < cnt - 1; j++) {
union(party.get(j), party.get(j + 1));
}
}
if (truthPeople.isEmpty()) {
System.out.println(M);
return;
}
Set<Integer> truthRoots = new HashSet<>();
for (int x : truthPeople) {
truthRoots.add(find(x));
}
int ans = 0;
for (List<Integer> party : parties) {
boolean flag = true;
for (int p : party) {
if (truthRoots.contains(find(p))) {
flag = false;
break;
}
}
if (flag) ans++;
}
System.out.println(ans);
}
}728x90
반응형
'✏️ > BOJ' 카테고리의 다른 글
| [BOJ/Simulation] 백준 14499 - 주사위 굴리기 (Java) (0) | 2025.12.05 |
|---|---|
| [BOJ/Simulation] 백준 14891 - 톱니바퀴 (Java) (0) | 2025.12.05 |
| [BOJ/Graph] 백준 5214 - 환승 (Java) (0) | 2025.12.04 |
| [BOJ/PriorityQueue] 백준 1781 - 컵라면 (Java) (0) | 2025.12.01 |
| [BOJ/Floyd-Warshall] 백준 1507 - 궁금한 민호 (Java) (0) | 2025.11.28 |