문제 이해

1차 코드

/*
 * 2025-07-03
 * 문제52_백준 B1043번
 * */

package day8.B1043;

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

public class Main {
    public 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 truthCnt = Integer.parseInt(st.nextToken());
        if(truthCnt != 0){
            int truthNum = Integer.parseInt(st.nextToken());
        }

        ArrayList<Integer>[] array = new ArrayList[m];

        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int partyCnt = Integer.parseInt(st.nextToken());

            array[i] = new ArrayList<>();
            for(int j = 0; j < partyCnt; j++){
                array[i].add(Integer.parseInt(st.nextToken()));
            }
        } // 입력 받기

        parent = new int[n + 1];
        for(int i = 0; i <= n; i++){
            parent[i] = i;
        }

        // 음 arrayList의 길이가 2이상이라면 union
        for(ArrayList<Integer> party : array){
            if(party.size() >= 2){
                for(int i = 0; i < party.size() - 1; i++) {
                    union(party.get(i), party.get(i + 1));
                }
            }
        }
        // 그리고 find( ) 가 딱 하나인것만 count해서 출력
        // -? 이건 어케하지?
        

        br.close();
    }

    /**
     * union-find
     * */
    static int find(int x){
        if(parent[x] != x){
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    /**
     * find
     * */
    static void union(int a, int b){
        int rootA = find(a);
        int rootB = find(b);

        if(rootA != rootB){
            parent[rootB] = rootA;
        }
    }
}

아 생각해보니 전에 문제에서도 중요했던게 boolean type을 하나 두고 true false 나누는 거였다

그러면 여기서도 진실알고 모르고 를 boolean으로 두어서 생각해보자

그리고 생각해보면 이번엔 ROOT(0)를 뭘로 두냐가 문제인데, 일단 진실을 아는 사람을 ROOT로 두고 풀어야겠지.

Q) 진실을 아는 사람이 여러명이면 root 가 여러개다. → 맞아?

A) 거기까지는 맞는데, 이제 진실 아는 사람끼리 UNION 해서 ROOT를 하나로 합쳐야 함.

2차 코드

이 부분을 모르겠음.

int result = 0;
for (ArrayList<Integer> party : array) {
    boolean canLie = true;
    for (int person : party) {
        for (int truthPerson : truthNum) {
            if (find(person) == find(truthPerson)) {
                canLie = false;
                break;
            }
        }
        if (!canLie) break; // 진실 아는 사람과 연결된 사람 발견 시 중단
    }
    if (canLie) result++; // 진실 아는 사람과 연결된 사람이 아무도 없을 경우
}

System.out.println(result);