1043번: 거짓말 (BOJ JAVA)

1043번: 거짓말

사용 언어: JAVA

 

풀이

파티에서 진실을 아는 사람을 좀비라 생각하고, 좀비와 같은 파티에 간 사람은 감염된다고 생각했다. 이 문제에 다시 와서 parent 함수, find-union으로 더 간단한 풀이를 만들어야겠다.

//진실을 아는 사람(좀비)과 같은 파티에 있던 사람은 감염된다.

import java.util.Scanner;

public class Main{
    
    static int[][] party;
    static int[] arr;
    static int[] arr2;
    
    public static void check_infect(int N, int M){ //N: how many people, M: party
        for(int i=0; i<M; i++){
            for(int j=0; j<arr2[i]; j++){
                if(arr[party[i][j]] == 1){
                    for(int k=0; k<arr2[i]; k++){
                        arr[party[i][k]] = 1;
                    }
                    break;
                }
            }
        }
    }

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt(); //N = Number of People
		int M = scan.nextInt(); //M = Number of Party
		int ans = M;
        boolean isZombie_flag = false;
		arr = new int[N+1]; //is person infected
        party = new int[M][N+1]; //who is at each party
        arr2 = new int[M]; //how many people at each party
		int HowManyKnowTruth = scan.nextInt();

		for(int i=0; i<HowManyKnowTruth; i++) {
			int NumberWhoKnowTruth = scan.nextInt();
			arr[NumberWhoKnowTruth] = 1;
		}
		for(int i=0; i<M; i++) {
            isZombie_flag = false; 
			int HowManyAtParty = scan.nextInt();
            arr2[i] = HowManyAtParty;
            int[] temparr = new int[HowManyAtParty];
			for(int j=0; j<HowManyAtParty; j++) {
				int WhoIsAtParty = scan.nextInt();
                temparr[j] = WhoIsAtParty;
                party[i][j] = WhoIsAtParty;
				if(arr[WhoIsAtParty] == 1) { //좀비가 존재
                    isZombie_flag = true;
				}
			}
            
            if(isZombie_flag == true){
                for(int j=0; j<HowManyAtParty; j++){
                    arr[temparr[j]] = 1; //좀비가 같은 파티에 있던 사람 감염을 함
                }
            }
		}
        
        //2차감염이나 그 이상이 있는지 확인해야함, 재귀로 감염이 나오면 안 나올때까지 계속 돌려야함
        for(int i=0; i<M; i++){
            check_infect(arr2[i], M);
        }

        for(int i=0; i<M; i++){
            for(int j=0; j<N; j++){
                if(arr[party[i][j]] == 1){ //어떠한 파티에 감염된 사람이 한명이라도 있으면 파티 취소
                    ans--;
                    break;
                }
            }
        }

		System.out.println(ans);
		
		scan.close();
	}
}