거짓말 - 1043번

---

풀이 방법

사람 수가 50까지로 비교적 적기 때문에 플로이드 워셜을 이용해서 사람끼리 연결되어 있는지 확인해주었다.

그 후 파티에 있는 사람마다 진실을 아는 사람과 연결되어 있는지 체크해서 count 해주었다.

 

내 코드

package com.company;

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

public class Main {
    static int N, M, K;

    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());
        int[][] p = new int[N + 1][N + 1];
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        for (int i = 0; i < M; i++) {
            list.add(new ArrayList<Integer>());
        }

        st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());
        int[] arr = new int[K];

        for (int i = 0; i < K; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            p[arr[i]][arr[i]] = 1;
        }

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

            for (int j = 0; j < man; j++) {
                list.get(i).add(Integer.parseInt(st.nextToken()));
            }

            for (int j : list.get(i)) {
                for (int k : list.get(i)) {
                    if (j == k)
                        continue;
                    p[j][k] = 1;
                }
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                for (int k = 1; k <= N; k++) {
                    if (p[j][i] == 1 && p[i][k] == 1) {
                        p[j][k] = 1;
                    }
                }
            }
        }

        int count = 0;

        for (int i = 0; i < list.size(); i++) {
            boolean check = true;
            for (int j = 0; j < list.get(i).size(); j++) {
                for (int k = 0; k < arr.length; k++) {
                    if(check && p[list.get(i).get(j)][arr[k]] == 1){
                        check = false;
                        break;
                    }
                }
            }
            if(check){
                count++;
            }
        }

        System.out.println(count);
    }
}