[BOJ] 1043. 거짓말

유니온파인드를 이용하는 문제였다.

문제를 맨처음 접근함에 있어서 파티의 순서가 보장된다고 생각하여 단순하게 생각하였지만, 테스트 케이스를 보고 파티의 순서가 보장되지 않음을 알게 되었고 다시 생각하게 되었다. 다시 생각해보니 같은 파티마다 서로 연결되는 성질을 보았을 떄 유니온파인드가 생각이 나서 적용을 해보았다. 

우선 파티의 인원을 전부 입력을 받고, 파티마다 참석자들을 union 해주었다. 그 후 이미 진실을 알고 있는 자 들과 파티의 참석자간의 루트값을 비교하여서 진실을 알고있는 사람들을 모두 선별해주고, 그것을 기준으로 거짓을 얘기할 수 있는 파티를 찾았다. 유니온파인드를 사용할때 주의할점이 있는데 서로의 루트 노드가 같은지를 확인할 때에는 단순히 p[i] , p[j] 값을 비교하는게 아니라 find(i), find(j)를 비교해주어야 한다. 이 부분을 주의할 필요가 있다.

package algosutdy1;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main_bj_1043_거짓말 {
    static int[] p;
    static int N, M;
    static List<Integer> knowList;
    static int[][] party;
    static int answer;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());    //전체사람수
        M = Integer.parseInt(st.nextToken());    //파티수
 
        //정답아는 사람 입력
        st = new StringTokenizer(br.readLine());
        knowList = new ArrayList<>();
        int knowPeople = Integer.parseInt(st.nextToken());
        for (int i = 0; i < knowPeople; i++) {
            knowList.add(Integer.parseInt(st.nextToken()));
        }
 
        //파티 입력
        party = new int[M][N];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int partyPeople = Integer.parseInt(st.nextToken());
 
            for (int j = 0; j < partyPeople; j++) {
                party[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        makeConnections();
 
        answer = 0;
        checkPossible();
        System.out.println(answer);
    }
 
    static void makeConnections() {
        p = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            p[i] = i;
        }
 
        for (int i = 0; i < M; i++) {
            int cur = party[i][0];
 
            for (int j = 1; j < N; j++) {
                int next = party[i][j];
 
                if (cur != 0 && next != 0) {
                    union(cur, next);    //같은 파티에 참여한 사람들에 한해서 같은 p를 가질수있도록 union
                    cur = next;
                }
            }
        }
    }
 
    static void checkPossible() {
        List<Integer> newKnowList = new ArrayList<>();
 
        //connection이 일어난 후 정답을 알고있는 모든 사람을 확인
        for (int i = 1; i <= N; i++) {
            for (Integer know : knowList) {
                if (find(i) == find(know)) {    //단순 p값 비교 말고 루트값을 find로 찾아서 비교
                    newKnowList.add(i);
                    break;
                }
            }
        }
 
        for (int i = 0; i < M; i++) {
            boolean possible = true;
            for (int j = 0; j < N && possible; j++) {
                int person = party[i][j];
 
                if (newKnowList.contains(person)) {
                    possible = false;
                }
            }
            if (possible) {
                answer++;
            }
        }
    }
 
    static int find(int num) {
        if (p[num] == num) {
            return num;
        }
 
        return p[num] = find(p[num]);
    }
 
    static void union(int num1, int num2) {
        num1 = find(num1);
        num2 = find(num2);
 
        if (num1 < num2) {
            p[num2] = num1;
        } else {
            p[num1] = num2;
        }
 
    }
}