[백준]1043_거짓말 Java 풀이

사이트 링크

1043번: 거짓말

1043번: 거짓말

 

 

개념 및 풀이

유니온파인드를 이용한 문제.

1. 진실을 아는 사람들을 같은 그룹으로 묶어줌(union)
2. 같은 파티에 있는 사람들을 같은 그룹으로 묶어줌(union)
3. 이 과정에서 진실을 아는 사람이 있는 파티는 알아서 진실을 아는 그룹과 같이 될 것임
4. 파티를 돌면서 진실을 아는 한 사람과 해당 파티가 같이 묶여있는지 확인

 

 

코드

package UnionFind;

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

public class Main_1043 {
    static int N,M,tn,pn,tList[],parents[];
    static ArrayList<Integer>[] party;
    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());

        makeSet();

        st = new StringTokenizer(br.readLine());
        tn = Integer.parseInt(st.nextToken());
        tList = new int[tn];
        for (int i = 0; i < tn; i++) {
            tList[i] = Integer.parseInt(st.nextToken());
            // 진실을 아는 사람을 한 묶음으로
            if(i != 0) union(tList[0],tList[i]);
        }

        int answer = 0;
        if(tn == 0) {
            System.out.println(M);
            return;
        }

        party = new ArrayList[M];
        boolean[] trueParty = new boolean[M];
        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());
            pn = Integer.parseInt(st.nextToken());
            party[m] = new ArrayList<>();

            int a = Integer.parseInt(st.nextToken());
            party[m].add(a);
            for (int i = 1; i < pn; i++) {
                int b = Integer.parseInt(st.nextToken());
                party[m].add(b);
                // 같은 파티에 있는 사람 union
                // -> 진실을 아는 사람이 있다면 자연스럽게 같은 묶음으로 됨
                union(a,b);
            }

        }

        for (int i = 0; i < M; i++) {
            //boolean know = false;
            //for (int j = 0; j < tn; j++) {
            //    // 진실을 아는 사람과 해당 파티의 사람(각 파티 사람들은 모두 같은그룹)이 묶여있는지 확인
            //    if(party[i].size() != 0 && !know(party[i].get(0),tList[j])) {
            //        know = true;
            //        break;
            //    }
            //}
            //if(!know) answer++;
						if(know(party[i].get(0),tList[0])) {
                answer++;
            }
        }
        System.out.println(answer);

    }
    static boolean know(int a, int b) {
        int aRoot = findSet(a);
        int bRoot = findSet(b);
        if(aRoot == bRoot) return false;
        return true;
    }
    static void makeSet() {
        parents = new int[N+1];
        for (int i = 1; i <= N; i++) {
            parents[i] = i;
        }
    }
    static int findSet(int a) {
        if(a==parents[a]) return a;
        return parents[a] = findSet(parents[a]);
    }

    static boolean union(int a,int b) {
        int aRoot = findSet(a);
        int bRoot = findSet(b);
        if(aRoot == bRoot) return false;

        parents[bRoot] = aRoot;
        return true;
    }
}