[알고리즘] 유니온 파인드

백준 1043

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

public class Main {

	static int[] parents;
	static List<Integer> eList;
	public static void main(String[] args) throws IOException{
		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());
		
        // n+1인 이유 => 인덱스와 번호를 맞추기 위함
		parents = new int[n+1];
		for(int i=1; i<n+1; i++) {
			parents[i] = i;
		}
		st = new StringTokenizer(br.readLine());
		int en= Integer.parseInt(st.nextToken());
        
        // 진실을 아는 사람을 담은 리스트
		eList = new ArrayList<>();
		if(en==0) {
			System.out.println(m);
			return;
		}
		else{
			for(int i=0; i<en; i++) {
				eList.add(Integer.parseInt(st.nextToken()));
			}
		}
		
        // 각 파티에 참가한 사람들을 담을 리스트 배열(외계인 문제에서 줄마다 stack을 할당하기 위해 스택 배열을 생성하는 원리와 동일)
		List<Integer>[] partyList = new ArrayList[m];
		for(int i=0; i<m; i++) {
			partyList[i] = new ArrayList<>();
		}
		
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int pn = Integer.parseInt(st.nextToken());
			
			int x = Integer.parseInt(st.nextToken());
			partyList[i].add(x);
			for(int j=1; j<pn; j++) {
				int y = Integer.parseInt(st.nextToken());
				union(x,y);
				partyList[i].add(y);
			}
		}
        
		int cnt=0;
		for(int i=0; i<m; i++) {
			boolean flag = true;
			for(int num : partyList[i]) {
				if(!check(num)) {
                    flag = false;
                    break;
    			}
            }
			if(flag) {
				cnt++;
			}
		}
		System.out.println(cnt);
		
	}
	
    // 유니온 파인드 find 메서드
	static int find(int x) {
		if(parents[x] ==x) return x;
		return find(parents[x]);
	}
	
    // 유니온 파인드 union 메서드
	static void union(int x, int y) {
        x = find(x);
		y = find(y);
		if(x!=y) {
            parents[y]=x;
        }
	}
    
    // 파라미터로 넘어온 값의 부모를 찾고, 진실을 아는 사람을 하나씩 꺼내서 부모를 찾은 후 두 값이 같다면 거짓말 불가
    static boolean check(int x){
        x = find(x);
        for(int y : eList){
            if(x == find(y)) return false;
        }
        return true;
    }
}

얻어갈 점:

• 유니온 파인드를 쓸 수 있는 point => 진실을 알고 있는 사람과 한 번이라도 같은 파티라면 거짓말 불가능 => 그룹핑을 통해 한 번이라도 같은 파티였는지, 아닌지 묶는 알고리즘? => 유니온 파인드
• 유니온 파인드를 묶기 위해서는 union(x,y)와 같이 파라미터 2개 넘겨야 하기 때문에 이중 for문에서 외부 for문에서 하나를 미리 입력 받고 내부 for문에서 입력 받아 넘기는 형식 이용 / (1,2) (1,3) (1,4) --
• 유니온 파인드 알고리즘에서 find 메서드가 필수인 이유? parents 배열의 값만을 보고 누가 연결되어있는지 확실치 않기 때문에 find 메서드에서 재귀 호출을 해 parent 노드를 검색해야함