아이디어

• 같은 파티에 참여한 사람들은 같은 집합으로 묶는다.
  • 최초로 진실을 아는 사람은 집합 0에 있다고 하자.
  • 예를 들어 진실을 아는 사람과 같은 파티에 있던 모든 사람은 집합 0(진실을 앎)에 속하게 된다.
  • 진실을 알고 있을 때 항상 대표자가 집합 0이 되도록 union 함수는 가장 작은 수를 참조하도록 해야 한다.
• 이후 모든 파티에 대해, 참여자 모두가 진실을 모르는 파티에 대해서만 과장된 말을 한다.
• 위 두 단계는 동시에 실행하지 않고 반드시 집합을 모두 묶은 후 말을 해야 한다.
  • 따라서 파티 입력을 먼저 자료구조에 저장한 뒤 해당 자료구조를 참조하는 방식으로 구현해야 한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tk = null;

	static int N, M, k, ans;
	static List<List<Integer>> queries = new ArrayList<>();
	static int[] parent;
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = Integer.parseInt(tk.nextToken());
		M = Integer.parseInt(tk.nextToken());
		
		// 진실 아는 사람 세팅
		makeSet();
		tk = new StringTokenizer(rd.readLine());
		int k = Integer.parseInt(tk.nextToken());
		for (int i=0; i<k; i++) {
			int p = Integer.parseInt(tk.nextToken());
			parent[p] = 0;
		}
		
		// 입력 저장
		for (int i=0; i<M; i++) {
			List<Integer> party = new ArrayList<>();
			
			tk = new StringTokenizer(rd.readLine());
			k = Integer.parseInt(tk.nextToken());
			for (int j=0; j<k; j++) {
				int p = Integer.parseInt(tk.nextToken());
				party.add(p);
			}
			queries.add(party);
		}
		
		// union-find
		// 파티에 참여한 모든 사람을 같은 집합에 묶음
		for (List<Integer> party: queries) {
			int prev = party.get(0);
			k = party.size();
			for (int j=1; j<k; j++) {
				int p = party.get(j);
				union(prev, p);
				prev = p;
			}
		}
		
		// 집합 
		Q_LOOP: for (List<Integer> party: queries) {
			for (int p: party) {
				if (findSet(p) == 0) continue Q_LOOP;
			}
			ans++;
		}
		
		System.out.println(ans);
	}
	
	static void makeSet() {
		parent = new int[N+1];
		for (int i=1; i<=N; i++)
			parent[i] = i;
	}
	
	static int findSet(int x) {
		if (parent[x] == x) return x;
		return parent[x] = findSet(parent[x]);
	}
	
	// union은 작은 번호로 병합해야 함
	static boolean union(int x, int y) {
		int px = findSet(x);
		int py = findSet(y);
		if (px == py) return false;
		if (px < py) parent[py] = px;
		else parent[px] = py;
		return true;
	}
}

메모리 및 시간

• 메모리: 14240 KB
• 시간: 124 ms

리뷰

• 첫 번째 시도: bitmasking을 이용한 집합 표현
  • 진실을 아는 사람의 집합을 따로 만드는 방법을 시도했다.
  • 그러나 진실이 알려질 때 이전에 참여했던 파티 참가자들에게 처리를 할 수 없다는 문제가 있었다.