풀이 방법
사람 수가 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);
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
줄어들지 않아 - 2688번 (0) | 2021.11.09 |
---|---|
팀 배정 - 18768번 (0) | 2021.11.08 |
십자가 2개 놓기 - 17085번 (0) | 2021.11.05 |
Coins - 3067번 (0) | 2021.11.04 |
뱀 - 3190번 (0) | 2021.11.02 |