[BOJ][Java] 1043번 거짓말

문제 설명

 

문제 링크 : https://www.acmicpc.net/problem/1043

 

문제를 살펴보면 처음에는 단순히 진실을 말해야 하는 사람들이 포함되어 있는 파티에 참여한 모든 사람들에게만

진실을 말해야 한다고 생각할 수 있다.

 

위의 예제는 보면 진실되게 말해야만 하는 사람이 포함되어있지 않은 상태이다.

이럴 때는 모든 파티에서 과장되게 말해도 된다.

예제 5번

이번에는 예제 5번을 보자

여기서 1, 2, 3, 4번은 이미 진실을 알고 있는 사람들이다.

따라서 첫 번째 파티의 참여한 1, 5번 중 5번은 진실을 모르는 사람이지만 

1번이 포함되어있기때문에 지민이는 진실을 말해야 하고 따라서 5번도 

진실을 알게된 사람이 된다. 

 

만약 5번이 임의의 파티에 참석했다고 가정하자

해당 파티에는 이미 진실을 알고 있는 1, 2, 3, 4번이 모두 없다.

하지만 지민이는 5번이 파티에 있기 때문에

진실만을 말해야한다.

 

이런 식으로 어떤 파티에 참여한 것 자체가 진실을 아는지 모르는지의 기준점이 된다.

따라서 이 문제는 몇 번째 파티에 참여한 것이 일종의 집합이 되므로

유니온 파인드를 이용하면 문제를 해결할 수 있다.

 

package boj;

import java.util.*;
import java.io.*;

public class BOJ1043 {
    static int[] trueP;
    static int[] heads;
    static boolean[] trueNode;
    static List<List<Integer>> list = new ArrayList<>();
    public static void main(String[] args) throws Exception {
        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());

        st = new StringTokenizer(br.readLine());
        int t = Integer.parseInt(st.nextToken());


        trueP = new int[t];
        trueNode = new boolean[N+1];
        int answer = 0;

        for(int i = 0 ; i < t; i++){
            trueP[i] = Integer.parseInt(st.nextToken());
        }

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

        for(int i = 0; i < M; i++){
            List<Integer> temp = new ArrayList<>();
            st = new StringTokenizer(br.readLine());
            st.nextToken();

            while(st.hasMoreTokens()){
                temp.add(Integer.parseInt(st.nextToken()));
            }
            for(int j = 0; j < temp.size() - 1; j++){
                union(temp.get(j), temp.get(j+1));
            }
            list.add(temp);
        }

        for(int i = 0; i < trueP.length; i++){
            trueNode[find(trueP[i])] = true;
        }

        for(int i = 0; i < list.size(); i++){
            if(check(list.get(i))) answer++;
        }

        System.out.println(Arrays.toString(heads));
        System.out.println(answer);


    }
    static void union(int a, int b){
        int aHead = find(a);
        int bHead = find(b);

        if(aHead != bHead) heads[bHead] = aHead;
    }


    static int find(int node){
        if(node == heads[node]) return node;
        return heads[node] = find(heads[node]);
    }

    static boolean check(List<Integer> target){
        for(int i = 0; i < target.size(); i++){
            if(trueNode[find(target.get(i))]) return false;
        }
        return true;
    }
}