1043번: 거짓말
지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게
www.acmicpc.net
- 풀이
bfs방식으로 party를 돌아가며 겹치는 사람들까지 검사하며 솔직하게 말해야 되는 party가 있으면 총 파티 수에서 마이너스
- 코드
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int N, M, answer;
static ArrayList<Integer>[] array;
static boolean[] check, partyCheck;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(answer);
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
N = in.nextInt();
M = in.nextInt();
answer = M;
check = new boolean[N + 1];
partyCheck = new boolean[M];
array = new ArrayList[M];
int truesNumber = in.nextInt();
for (int i = 0; i < truesNumber; i++) {
check[in.nextInt()] = true;
}
for (int i = 0; i < M; i++) {
array[i] = new ArrayList<Integer>();
int size = in.nextInt();
for (int j = 0; j < size; j++) {
array[i].add(in.nextInt());
}
}
SaveAnswer();
}
public static void SaveAnswer() {
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i <= N; i++) {
if (check[i]) queue.add(i);
}
while (!queue.isEmpty()) {
int now = queue.poll();
for (int i = 0; i < M; i++) {
if (partyCheck[i] || !array[i].contains(now)) continue;
partyCheck[i] = true;
answer--;
for (int j = 0; j < array[i].size(); j++) {
int next = array[i].get(j);
if (check[next]) continue;
check[next] = true;
queue.offer(next);
}
}
}
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}'algorithm' 카테고리의 다른 글
| [BOJ/JAVA] 백준 1717번 : 집합의 표현 (0) | 2021.08.12 |
|---|---|
| [BOJ/JAVA] 백준 17298번 : 오큰수 (0) | 2021.08.11 |
| [BOJ/JAVA] 백준 2003번 : 수들의 합 2 (0) | 2021.08.10 |
| [BOJ/JAVA] 백준 1074번 : Z (0) | 2021.08.10 |
| [BOJ/JAVA] 백준 1992번 : 쿼드트리 (0) | 2021.08.10 |
