백준 1043 거짓말 자바

문제는 다음과 같다.
https://www.acmicpc.net/problem/1043


풀이는 다음과 같다.

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

public class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); //사람수
        int m = Integer.parseInt(st.nextToken()); //파티수

        ArrayList<Integer>[] party = new ArrayList[m+1]; //파티 인원들 넣어줄거야
        ArrayList<Integer>[] A = new ArrayList[n+1]; //서로 만나게되는거 그래프

        for(int i = 1 ; i <= m ; i++) {
            party[i] = new ArrayList<>();
        }

        for(int i = 1 ; i <= n ; i++) {
            A[i] = new ArrayList<>();
        }

        boolean[] avoid = new boolean[n+1];
        //첫줄 여기까지
        
        
        ArrayList<Integer> arr = new ArrayList<>(); //진실 아는 사람들
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        int good = Integer.parseInt(st1.nextToken()); //진실 아는 사람 수
        
        for(int i = 0 ; i < good ; i++) {
            int cur = Integer.parseInt(st1.nextToken());
            avoid[cur] = true;
            arr.add(cur);
        }
        //둘째줄여기까지
        
        for(int i = 1 ; i <= m ; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st2.nextToken()); //파티 인원 수
            
            for(int j = 0 ; j < a ; j++) {
                party[i].add(Integer.parseInt(st2.nextToken()));
            }
        }
        //입력 여기까지
        
        //같은 파티인 친구들 이어주는 그래프 만들어주기
        for(int i = 1 ; i <= m ; i++) {
            for(int j = 0 ; j < party[i].size()-1 ; j++) {
                int a = party[i].get(j);
                int b = party[i].get(j+1);
                A[a].add(b);
                A[b].add(a);
            }
        }



        for(int i = 1 ; i <= n ; i++) {
            if(avoid[i]) {
                Queue<Integer> q = new LinkedList<>();
                boolean[] visited = new boolean[n+1];
                q.add(i);
                visited[i] = true;

                while(!q.isEmpty()) {
                    int cur = q.poll();

                    for(int next : A[cur]) {
                        if(!visited[next]) {
                            q.add(next);
                            visited[next] = true;
                            avoid[next] = true;
                        }
                    }
                }
            }
        }
        //피할 친구들 avoid에 기록


        int answer = 0;

        //파티 순회하며 피할 친구들 업스면 거짓말 가능이니 answer++;
        for(int i = 1 ; i <= m ; i++) {
            boolean fake = true;
            for(int human : party[i]) {
                if(avoid[human]) {
                    fake = false;
                    break;
                }
            }

            if(fake) answer++;

        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
    }


}

풀이 로직은 다음과 같다.

진실을 알고 있는 친구가 포함된 파티에선 무조건 진실만을 말해야 한다.
또한,
한번 진실을 들은 친구들에게는 계속해서 진실만을 이야기해야 한다.

즉,
맨 처음 진실을 알고 있는 친구가 가는 파티,
그 파티에 참여하는 사람들,
그 사람들이 참여하는 또다른 파티,..
계속해서 진실을 말해야 한다.

진실된 친구들의 카르텔을 형성하는 로직은 아래와 같다.
해당 로직을 거치면, 진실을 말해야하는 모든 친구들을 체크할 수 있다.

for(int i = 1 ; i <= n ; i++) {
            if(avoid[i]) { //피해야 할 친구라면 BFS로직으로 친구들까지 전부 체크
                Queue<Integer> q = new LinkedList<>();
                boolean[] visited = new boolean[n+1];
                q.add(i);
                visited[i] = true;

                while(!q.isEmpty()) {
                    int cur = q.poll();

                    for(int next : A[cur]) {
                        if(!visited[next]) {
                            q.add(next);
                            visited[next] = true;
                            avoid[next] = true;
                        }
                    }
                }
            }
        }
        //피할 친구들 avoid에 기록

이제 피할 사람들을 골라냈으니,
avoid에 true로 기록된 친구들에게 거짓말 하는것은 피해야 한다.

즉, 어떤 파티의 구성원 모두의 avoid가 false라면, 거짓말을 해도 된다.
해당 로직은 아래와 같다.

//파티 순회하며 피할 친구들 업스면 거짓말 가능이니 answer++;
        for(int i = 1 ; i <= m ; i++) {
            boolean fake = true;
            for(int human : party[i]) {
                if(avoid[human]) {
                    fake = false;
                    break;
                }
            }

            if(fake) answer++;

        }

이 문제는 입력값을 받아 사용하기가 약간 까다롭다고 생각하는 문제이다.