[Algorithm] 백준_거짓말_1043번 (JAVA) 유니온 파인드

📝문제

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

거짓말: 1043번

티어: 골드 4

💡풀이

문제 유형

유니온파인드

 

걸린 시간

60분

 

시간 복잡도

O(N+M)

 

풀이 방법 도출

1. 이 문제의 키포인트: 진실을 알고있는 사람끼리 묶기

2. hashset에 진실을 알고 있는 사람을 add한다.

3. 같은 파티에 있는 사람들은 모두 같은 집합으로 묶는다. union

4. 진실을 아는 사람의 최상위 부모를 새로운 set에 넣고

5. 파티 별 사람들을 검색해 사람들의 최상위 부모가 set에 포함되어있는지 확인한다.

import java.util.*;
import java.io.*;
class Main{
    static int[] parent;
    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());

        parent = new int[N+1];
        for(int i = 0; i <= N; i++){
            parent[i] = i;
        }

        ArrayList<Integer>[] person = new ArrayList[M+1];
        for(int i = 0; i <= M; i++){
            person[i] = new ArrayList<>();
        }

        HashSet<Integer> set = new HashSet<>();
        st = new StringTokenizer(br.readLine());
        int knowTruthPeople = Integer.parseInt(st.nextToken());
        for(int i = 0; i < knowTruthPeople; i++){
            set.add(Integer.parseInt(st.nextToken()));
        }

        for(int i = 1; i <= M; i++){
            st = new StringTokenizer(br.readLine());
            int count = Integer.parseInt(st.nextToken());
            int prev = -1;
            for(int j = 0; j < count; j++){
                int p = Integer.parseInt(st.nextToken());
                person[i].add(p);
                if(prev != -1){
                    union(prev, p);
                }else{
                    prev = p;
                }
            }
        }

        HashSet<Integer> set2 = new HashSet<>();
        for (int p : set) {
            set2.add(find(p));
        }

        int answer = M;

        for(int i = 1; i <= M; i++){
            for(int p : person[i]){
                if(set2.contains(find(p))){
                    answer--;
                    break;
                }
            }
        }

        System.out.println(answer);
    }
    public static int find(int a){
        if(parent[a] == a){
            return a;
        }
        return parent[a] = find(parent[a]);
    }
    public static void union(int a, int b){
        int rootA = find(a);
        int rootB = find(b);

        if(rootA != rootB){
            parent[rootB] = rootA;
        }
    }
}

 

🤔Review

처음에 이 문제를 풀며 이렇게 쉬운 문제가 왜 골드지? 했는데 아니나 다를까 접근방법이 완전히 달랐던 것..

유니온 파인드 아직 낯설지만, 알고리즘 연습 굳,