[Java] 백준 1043번 : 거짓말

1. 문제

https://www.acmicpc.net/problem/1043

1043번: 거짓말

 

 

 

2. 풀이과정

1. 파티 정보를 Queue에 넣고, 결과는 Queue의 사이즈를 출력한다.

2. 진실을 아는 사람은 집합(set)으로 관리한다.

3. Queue에서 파티 하나를 꺼내서 거짓말 할 수 있는지 check

    1) 파티의 참여자 중 set에 포함된 사람이 있으면 해당 파티 참여자도 set에 넣는다.

    2) set에 한 명도 포함되지 않으면, 다시 queue에 넣는다.

4. 진실을 아는 사람 정보(set의 크기)의 변화가 없으면 종료한다.

import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws Exception {
		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 truth = Integer.parseInt(st.nextToken());
		Set<Integer> set = new HashSet<>();
		for(int i=0; i<truth; i++) {
			set.add(Integer.parseInt(st.nextToken()));
		}
		//파티 정보
		Queue<Set<Integer>> parties = new LinkedList<>();
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			Set<Integer> participants = new HashSet<>();
			int cnt = Integer.parseInt(st.nextToken());
			for(int j=0; j<cnt; j++) {
				participants.add(Integer.parseInt(st.nextToken()));
			}
			parties.add(participants);
		}
		
		//연산
		int n = 0;
		while(n!=set.size() && parties.size()>0) {
			n = set.size();
			int size = parties.size();
			for(int i=0; i<size; i++) {
				Set<Integer> party = parties.poll();
				boolean ban = false;
				for(int su : party) {
					if(set.contains(su)) {
						ban = true;
						break;
					}
				}
				if(ban) {
					set.addAll(party);
				}
				else {
					parties.add(party);
				}
			}
				
		}
		System.out.println(parties.size());
	}

}

 

 

결과