[JAVA] 백준 1043 거짓말

 

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);
    }
}