
https://www.acmicpc.net/problem/1043
문제분석
진실을 알고 있는 사람만 조심해야 하는게 아니라, 진실을 알고 있는 사람이랑 "같이 파티하는 사람" 도 조심해야 한다. 쉽게 설명하자면, 진실을 알고 있는 사람이 진실을 퍼뜨린다. 그래서 거짓말을 하기 위해서는 진실을 알고 있는 사람과 아예 엮이지 않게끔 말해야 한다.
N= 50이니, while로 반복을 하면 O(N^2)이여도 2500회밖에 안된다. 따라서 while문을 활용하여 해결하였다.
코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args)throws IOException{
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 truthNum = Integer.parseInt(st.nextToken());
Set<Integer> truthSet = new HashSet<Integer>();
for(int i = 0; i < truthNum; i++){
truthSet.add(Integer.parseInt(st.nextToken()));
}
int oldSetSize = 0;
int[][] partyArr = new int[M][N+1]; // [[사람 번호, 사람 번호 ..],[사람 번호, 사람 번호 ..]..]
boolean[] partyFlag = new boolean[M]; // 파티 Flag, 말할 수 있는 파티만 true
Arrays.fill(partyFlag,true);
for(int i = 0; i < M; i++){
st = new StringTokenizer(br.readLine());
int num = Integer.parseInt(st.nextToken());
partyArr[i][0] = num;
for(int j = 0; j < num; j++){
partyArr[i][j+1]=Integer.parseInt(st.nextToken());
}
}
while(truthSet.size() != oldSetSize){// truthSet 숫자가 바뀌지 않을 때 까지 순회.
oldSetSize = truthSet.size();
for(int i = 0; i < M; i++){
int partyAttendance = partyArr[i][0];
boolean flag = false;
for(int j = 0; j < partyAttendance; j++){
int temp = partyArr[i][j+1];
if(truthSet.contains(temp)){ // 진실을 아는 사람이 이 파티에 존재하는경우
flag = true;
partyFlag[i]=false;
}
}
if(flag){ // flag가 true인 경우, 해당 파티 전 인원 추가.
for(int j = 0; j < partyAttendance; j++){
truthSet.add(partyArr[i][j+1]);
}
}
}
}
int result = M; // 기본값은 파티의 수로 초기화
for(int i = 0; i < M; i++){
if(!partyFlag[i]){
result-=1;
}
}
System.out.println(result);
}
}

'알고리즘&PS > PS' 카테고리의 다른 글
| [JAVA] 백준 1022 소용돌이 예쁘게 출력하기 (0) | 2026.02.13 |
|---|---|
| [JAVA] 백준 1360 되돌리기 (0) | 2026.02.12 |
| [JAVA] 백준 2413 비슷한 순열 (0) | 2025.09.22 |
| [JAVA] 백준 1135 뉴스 전하기 (0) | 2025.09.09 |
| [JAVA] 백준 1967 트리의 지름 (0) | 2025.09.06 |