이번에 풀어본 문제는
백준 1043번 거짓말 입니다.

📕 문제 링크

❗️코드

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

public class Main {
    static int N,M;
    static boolean [] truth;
    static List<List<Integer>> party;
    static int [] parents;
    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());

        party = new ArrayList<>();

        //진실을 아는 사람 수
        truth = new boolean[N + 1];
        st = new StringTokenizer(br.readLine());
        int tCount = Integer.parseInt(st.nextToken());
        
        //아는사람 없으면 출력 후 종료
        if (tCount < 1) {
            System.out.print(M);
            System.exit(0);
        }
        for (int i = 0; i < tCount; i++) {
            int tmpNumber = Integer.parseInt(st.nextToken());
            truth[tmpNumber] = true;
        }

        //자기 자신으로 초기화
        parents = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            parents[i] = i;
        }

        // 파티
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int tmpCount = Integer.parseInt(st.nextToken());

            List<Integer> partyMember = new ArrayList<>();
            for (int j = 0; j < tmpCount; j++) {
                int memberNumber = Integer.parseInt(st.nextToken());
                partyMember.add(memberNumber);
                if (j > 0) {
                    union(partyMember.get(j - 1), partyMember.get(j));
                }
            }
            party.add(partyMember);
        }

        boolean [] isVisited = new boolean[N + 1];
        for (int i = 1; i <= N; i++) {
            if (truth[i] && !isVisited[i]) {
                isVisited[i] = true;
                int parent = find(i);

                for (int j = 1; j <= N; j++) {
                    if (parent == find(j)) {
                        truth[j] = true;
                        isVisited[j] = true;
                    }
                }
            }
        }

        int answer = 0;
        next : for (List<Integer> list : party) {
            for (int member : list) {
                // 한명이라도 진실을 알면 다음파티로
                if (truth[member]) continue next;
            }
            answer++;
        }

        System.out.print(answer);
    }
    static int find(int child) {
        return parents[child] == child ? child : find(parents[child]);
    }

    static void union(int p, int c) {
        int parent = find(p);
        int child = find(c);

        if (parent != child) {
            parents[child] = parent;
        }
    }
}

📝 풀이

M번의 파티에서 거짓을 말할 수 있는 파티의 최댓값을 출력하는 문제입니다.
파티에 한 명이라도 진실을 아는 사람이 존재한다면, 해당 파티에서는 무조건 진실만을 말해야 하며, 나머지 참석자들도 진실을 알게 됩니다.
이를 정의하기 위해 입력된 M개의 파티를 탐색하면서 연관 관계를 union-find를 사용하여 완성시켜줍니다.
그 다음 진실을 알고있는 참석자를 담고있는 truth 배열의 값에 연관된 참석자들도 true로 변경해줍니다.
마지막으로, party를 전체 탐색하면서, 진실을 알고 있는 사람이 없는 파티를 찾아, 카운트를 올려주면 해결할 수 있습니다.

📜 후기

생각보다 많은 처리 과정이 필요한 문제였던 것 같습니다.