백준 1043번: 거짓말

문제 설명

• https://www.acmicpc.net/problem/1043
• 진실을 아는 사람이 포함된 집단에는 거짓말을 할 수 없습니다.
• 진실을 아는 사람과 함께 파티에 참석했던 사람이 포함된 집단에도 거짓말을 할 수 없습니다.

접근법

• 처음 생각: 거짓말을 간파한 사람이 포함된 파티 인원을 모두 거짓말을 간파한 사람으로 설정하면 되지 않을까?
• 처음 생각에 대한 반례) 1번이 거짓말쟁이라고 생각해 봅시다. 파티가 [1],[4],[1,4]가 들어온다면 2번째 [2]번 파티는 거짓말을 할 수 없는 파티로 취급되어야 합니다.
• 거짓말을 간파한 사람과 연관된 모든 나머지 사람들에게 거짓말을 할 수 없습니다. 위 예시처럼 어떤 사람(X)이 먼저 나오고 이후에 [간파한 사람, X]파티가 나오더라도 앞에 등장한 X사람이 속한 파티는 모두 거짓말을 할 수 없습니다.

Union-Find

	public static int find_parent(int[] parent, int x) {
		if(parent[x] == x) {
			return x;
		}else {
			parent[x] = find_parent(parent,parent[x]);
			return parent[x];
		}
	}
	
	public static void union(int a, int b,int[] parent) {
		int pa = find_parent(parent,a);
		int pb = find_parent(parent,b);
		if(pa>pb) {
			parent[pa] = pb;
		}else {
			parent[pb] = pa;
		}
	}

정답

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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] parent = new int[N+1];
		for (int i = 0; i < N+1; i++) {
			parent[i] = i;
		}
		int M = sc.nextInt();
		int t = sc.nextInt();
		int[] arr = new int[t];
		for (int i = 0; i < t; i++) {
			arr[i] = sc.nextInt();
		}
		List<int[]> group = new LinkedList<int[]>();
		for (int m = 0; m < M; m++) {
			int l = sc.nextInt();
			int[] temp = new int[l];
			for (int i = 0; i < l; i++) {
				temp[i] = sc.nextInt();
			}
			group.add(temp);
			if(l==1) continue;
			for (int i = 1; i < l; i++) {
				union(temp[i-1],temp[i],parent);
			}
		}
		for (int i = 0; i < N+1; i++) {
			find_parent(parent,i);
		}
		
		boolean[] answer = new boolean[N+1];
		Arrays.fill(answer, true);
		answer[0] = false;
		for (int i = 0; i < arr.length; i++) {
			int nowParent = parent[arr[i]];
			for (int j = 0; j < N+1; j++) {
				if(parent[j] == nowParent) {
					answer[j] = false;
				}
			}
		}
		int totalAnswer = 0;
		for (int i = 0; i < group.size(); i++) {
			totalAnswer += validCheck(group.get(i),answer);
		}
		System.out.println(totalAnswer);
		
	}
	
	public static int find_parent(int[] parent, int x) {
		if(parent[x] == x) {
			return x;
		}else {
			parent[x] = find_parent(parent,parent[x]);
			return parent[x];
		}
	}
	
	public static void union(int a, int b,int[] parent) {
		int pa = find_parent(parent,a);
		int pb = find_parent(parent,b);
		if(pa>pb) {
			parent[pa] = pb;
		}else {
			parent[pb] = pa;
		}
		
	}
	
	public static int validCheck(int[] g, boolean[] answer) {
		for (int i = 0; i < g.length; i++) {
			if(!answer[g[i]]) return 0;
		}
		return 1;
	}
}