백준 1043번 : 거짓말 java

이 문제는 지민이가 이야기하는 것에 대한 진실을 아는 사람이 주어질 때 이 사람들과 같은 파티에 갔던 사람들에게 들키지 않고 지민이가 얼마나 많은 파티에서 거짓말을 할 수 있는지 구하는 문제입니다.

이 문제를 풀 때 우선 지민이가 말한 것에 대한 진실을 아는 사람들을 입력받습니다.

그리고 그 사람들과 같은 파티에 갔던 사람들을 union-find를 이용하여 합쳐줍니다.

그리고 그 사람들이 갔던 파티를 제외한 다른 파티의 개수를 세어 출력하면 됩니다.

이에 대한 코드를 보여드리겠습니다.

---

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

public 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());

        st = new StringTokenizer(br.readLine());
        int knowNum = Integer.parseInt(st.nextToken());
        boolean[] knowPeople;

        //진실을 아는 사람이 없다면 파티의 수를 출력하고 바로 종료
        if(knowNum == 0){
            System.out.println(M);
            return;
        }
        //자신과 연결된 루트 노드를 설정
        parent = new int[N+1];
        for(int i = 1; i<=N; i++)
            parent[i] = i;

        //진실을 아는 사람들의 배열을 생성
        knowPeople = new boolean[N+1];
        for(int i = 0; i<knowNum; i++) {
            int num = Integer.parseInt(st.nextToken());

            knowPeople[num] = true;
        }

        //파티마다 참여한 사람들의 목록을 생성
        List<List<Integer>> partyList = new ArrayList<>();
        for(int i = 0; i<M; i++)
            partyList.add(new ArrayList<>());

        for(int i = 0; i<M; i++){
            st = new StringTokenizer(br.readLine());

            int num = Integer.parseInt(st.nextToken());
            for(int j = 0; j<num; j++) {
                partyList.get(i).add(Integer.parseInt(st.nextToken()));

                //같이 파티에 참가한 사람을 확인
                if(j != 0){
                    int nowIdx = partyList.get(i).get(j);
                    int exIdx = partyList.get(i).get(j-1);

                    union(exIdx, nowIdx);
                }
            }
        }

        boolean[] visited = new boolean[N+1];
        for(int i = 1; i<=N; i++){
            if(knowPeople[i] && !visited[i]) {
                int root = find(i);

                for (int j = 1; j <= N; j++) {
                    if(find(j) == root){
                        knowPeople[j] = true;
                        visited[j] = true;
                    }
                }
            }
        }

        //파티에 진실을 아는 사람이 있는지 확인
        boolean[] goParty = new boolean[M];
        for(int i = 0; i<M; i++)
            goParty[i] = true;

        for(int i = 0; i<M; i++){
            for(int j = 1; j<=N; j++){
                if(knowPeople[j]){
                    if(partyList.get(i).contains(j))
                        goParty[i] = false;
                }
            }
        }

        int sum = 0;
        for(int i = 0; i<M; i++)
            if(goParty[i])
                sum++;

        System.out.println(sum);
    }

    //자신과 연결된 노드의 루트 노드를 탐색
    static int find(int idx){
        if(parent[idx] == idx)
            return idx;
        else {
            parent[idx] = find(parent[idx]);
            return parent[idx];
        }
    }

    //연결된 노드가 다르다면 연결해줌
    static void union(int idx1, int idx2){
        int parent1 = find(idx1);
        int parent2 = find(idx2);

        if(parent1 != parent2)
            parent[parent2] = parent1;
    }
}

위의 내용과 같이 코드를 짜시면 됩니다.