[백준/1043] 거짓말 (골드 4) JAVA

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] NMSplit = br.readLine().split(" ");
        int N = Integer.parseInt(NMSplit[0]);
        int M = Integer.parseInt(NMSplit[1]);

        StringTokenizer st = new StringTokenizer(br.readLine());
        int catcherCount = Integer.parseInt(st.nextToken());
        List<Integer> catchers = new ArrayList<>();

        if (catcherCount != 0) {
            for (int i = 0; i < catcherCount; i++) {
                catchers.add(Integer.parseInt(st.nextToken()));
            }
        }
        List<Party> parties = new ArrayList<>();

        for (int i = 0; i < M; i++) {
            Party party = new Party();
            st = new StringTokenizer(br.readLine());
            int partyN = Integer.parseInt(st.nextToken());
            for (int j = 0; j < partyN; j++) {
                int partyMember = Integer.parseInt(st.nextToken());
                party.members.add(partyMember);
            }
            parties.add(party);
        }

        // 로직 시작
        // 첫 로직 - 명시된 catchers 포함된 party 조사
        Deque<Integer> deque = initLogic(catchers, parties);
        // deque에 든 놈들 지속해서 처리 해주기
        mainProcess(catchers, deque, parties);
        int canLieCount = 0;
        for (Party party : parties) {
            if (party.canLie) {
                canLieCount++;
            }
        }
        System.out.println(canLieCount);

    }

    private static void mainProcess(List<Integer> catchers, Deque<Integer> deque, List<Party> parties) {
        Set<Integer> visited = new HashSet<>(catchers);

        while (!deque.isEmpty()) {
            Integer poll = deque.poll();
            for (Party party : parties) {
                if (party.members.contains(poll)) {
                    party.canLie = false;
                    for (Integer member : party.members) {
                        if (!visited.contains(member)) {
                            visited.add(member);
                            deque.offer(member);
                        }
                    }
                }
            }
        }
    }

    private static Deque<Integer> initLogic(List<Integer> catchers, List<Party> parties) {
        Deque<Integer> deque = new ArrayDeque<>();
        for (Integer catcher : catchers) {
            for (Party party : parties) {
                if (party.members.contains(catcher)) {
                    party.canLie = false;
                    for (Integer member : party.members) {
                        if (!catchers.contains(member)) {
                            deque.offer(member);
                        }
                    }

                }
            }
        }
        return deque;
    }

    public static class Party {
        boolean canLie = true;
        Set<Integer> members = new HashSet<>();

        @Override
        public String toString() {
            return "Party{" +
                    "canLie=" + canLie +
                    ", members=" + members +
                    '}';
        }
    }

• 계속 읽어보니 그래프 + 구현 느낌이었음.
• 전염병처럼 번져나가는 스타일이네? -> BFS 이지 않을까
• 초기 제시로 준 아이들로 돌릴 deque 구성하고 deque가 빌때까지 BFS로직 돌려주면 된다.
• for문이 굉장히 많이 중첩되는데 party같은 객체 안만들고 하면 줄일 수 있지만 굳이? 문제 제시된 N,M 숫자 너무 작았음.
• 플로이드 알고리즘 같은것도 써볼수있나 싶었지만 파티와 인간은 같은 노드의 성질이 아니니까 포기
• 골드4 날먹문제같다.