[백준] 1043 거짓말 - 유니온파인드(Union Find) JAVA

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

1043번: 거짓말

코드설명

유니온파인드를 사용한 분리집합 문제입니다.

 

문제로직입니다.

1. 저는 문제에서 진실을 아는 집단은 parent[] = 0 이라고 선언하였습니다. 즉, 진실을 알고있다면 parent[x] = 0 입니다.
2. 각 입력마다 모든 분리집합을 연결시켜주기 위하여 각 파티에 참석하는 사람이 2명이상이라면 무조건 첫사람은 따로 입력받아서 unionParent(firstPeopleIdx, 나머지사람들 모두) 를 통하여 각 파티에 참석하는 사람들이 같은 곳을 바라보게 하였습니다. ( 이떄, parent[]가 모두 같아지지는 않을 수 있지만 이후에 findParent를 통하여 다 찾을 것이기에 같은 그룹으로만 보이도록 연결시켜주면 됩니다. )
3. 각 파티그룹을 돌면서 이제 실제로 거짓말을 할 수 있는지 체크합니다. 이떄, findParent를 통해서 이미 연결된 각 집합들이 0의 집합에 속한지, 아니면 다른 집합인지를 통하여 거짓말을 할 수 있는지 알 수 있습니다.

좋은 TC가 있습니다. ( https://www.acmicpc.net/board/view/72203 )

4 5
1 1
1 1
1 2
1 3
2 4 2
2 4 1

answer
1

과정
0 0 2 3 4
0 0 2 3 4
0 0 2 3 4
0 0 2 3 2

0 0 0 3 2 -> findParent를 통해서 0 0 2 3 0 이 아닌 0 0 0 3 2 입니다. findParent는 부모의 배열을 변화시킵니다.
또한 해당 로직을 사용하기 위해서 findParent를 통해서 같은 그룹인지 확인해야합니다. (제 코드에서는 Parent를 비교하는것이 아닙니다.)

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.regex.Pattern;

public class Main {
	public static int N, M;
	public static char[][] map;
	public static int answer = 0;
	public static int[] parent;
	public static int[] knowTruth;
	public static ArrayList<Integer>[] partyPeopleArr;
	
	public static int findParent(int x) {
		if( x == parent[x]) return x;
		return parent[x] = findParent(parent[x]);
	}
	
	public static void unionParent(int a, int b) {
		a = findParent(a);
		b = findParent(b);
		if( a < b ) parent[b] = a;
		else parent[a] = b;
	}
	
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	parent = new int[N+1];
    	for(int i=0; i<=N;i++) { //자기자신으로 초기화
    		parent[i] = i;
    	}
    	
    	st = new StringTokenizer(br.readLine());
    	int a = Integer.parseInt(st.nextToken());
    	for(int i=0;i<a;i++) {
    		unionParent(0, Integer.parseInt(st.nextToken()));
    	}
    	
    	
    	partyPeopleArr = new ArrayList[M];
    	for(int i=0;i<M;i++) {
    		partyPeopleArr[i] = new ArrayList<Integer>();
    	}
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		int peopleCnt = Integer.parseInt(st.nextToken());
    		
    		int firstPeopleIdx = Integer.parseInt(st.nextToken()); //처음의 값은 따로 받습니다.
    		partyPeopleArr[i].add(firstPeopleIdx);
    		for(int j=1; j<peopleCnt; j++) { //
    			int peopleIdx = Integer.parseInt(st.nextToken());
    			partyPeopleArr[i].add(peopleIdx);
    			unionParent(firstPeopleIdx, peopleIdx); //두개의 값 중 하나라도 진실을 안다면 그것에 맞추어 바뀌어질 것 입니다.  	
    		}
			
    	}
    	
    	for(int i=0;i<M;i++) { //이제 모든 파티를 돌면서 각 파티에 참석할 수 있는지 알아냅니다.
    		
    		boolean lieFlag = true;
    		for(int j=0;j<partyPeopleArr[i].size();j++) {
    			if(findParent(partyPeopleArr[i].get(j)) == 0) { //만약 한명이라도 진실을 안다면
    				lieFlag = false;
    				break;
    			}
    		}
    		if(lieFlag == true) {
    			System.out.println("WHY");
    			answer += 1;
    		}
    		
    	}
    	System.out.println(answer);
    }
}