BOJ 1043 : 거짓말 - https://www.acmicpc.net/problem/1043
input을 받으면서부터 엄청 헷갈렸던 문제다. n과 m이 주어진 뒤, 진실을 알고있는 사람 정보가 주어지고, 각 파티별 참석자 정보가 주어진다.
진실을 알고있는 사람(A)
과 같은 파티에 참석한 진실을 모르는 사람(B)
또한 진실을 듣게 된다. 그래서 이 진실을 모르지만 진실을 듣게된 사람(B)
이 모든 사람이 진실을 모르는 파티에 가게 된다면, 모든 사람이 진실을 알지 못하지만 그 파티에서는 과장되게 말할 수 없다. B가 다른 파티에서 진실을 들었기 때문에 모순이 생기기 때문이다.
우선 input을 받으며 파티 참석자의 정보를 저장하고, 파티 참석자 간 연관 관계를 나타내야했다. 그래프를 전부 그리기 보다는 각각의 사람이 연관관계가 있는지만 판단하면 됐기 때문에 union-find를 활용해서 parent 정보를 저장했다. (같은 parent를 가지면 이어져 있는 것으로 판단)
이후 진실을 아는 사람과 연관되어있다는 것은 진실을 듣는다는 것이기 때문에 각각 파티에서 진실을 듣는지, 과장된 이야기를 듣는지를 저장해둔다.
각 파티 별 참석자를 확인한다. 진실된 이야기를 들어야하는 사람이 한명이라도 있다면 패스하고, 아니라면 그 파티에서는 과장된 이야기를 할 수 있기 때문에 카운트 해준다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
public class Main {
static int[] parent;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = br.readLine().split(" ");
int n = Integer.parseInt(inputs[0]);
int m = Integer.parseInt(inputs[1]);
boolean[] people_know = new boolean[n+1]; // 알고있으면 T, 아니면 F
HashSet<Integer>[] parties = new HashSet[m+1];
for (int i = 1; i <= m; i++) {
parties[i] = new HashSet<>();
}
inputs = br.readLine().split(" ");
int know_num = Integer.parseInt(inputs[0]);
for (int i = 1; i <= know_num; i++) { // 진실을 아는사람 T
int tmp = Integer.parseInt(inputs[i]);
people_know[tmp] = true;
}
parent = new int[n + 1];
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
for (int p = 1; p <= m; p++) { // party number
inputs = br.readLine().split(" ");
int party_num = Integer.parseInt(inputs[0]); // 파티에 오는 사람 수
if(party_num<=1) {
parties[p].add(Integer.parseInt(inputs[1]));
continue;
}
for (int j = 1; j < party_num; j++) { // 연관 관계 이어줌
int a = Integer.parseInt(inputs[j]);
int b = Integer.parseInt(inputs[j+1]);
if (find(a) != find(b)) {
union(a,b);
}
parties[p].add(a); // 파티에 참여하는 사람 저장
parties[p].add(b);
}
}
// 진실을 아는 사람과 연관 관계 있음 => people_know[i] T로 변경
boolean[] visited = new boolean[n + 1];
for (int i = 1; i <= n; i++) {
if(people_know[i] && !visited[i]){
int root = find(i);
for (int j = 1; j <= n; j++){
if (find(j)==root) {
people_know[j] = true;
visited[j] = true;
}
}
}
}
// 모든 파티 참석자가 F여야 과장된 얘기를 할 수 있음
int result = 0;
for (int i = 1; i <= m; i++) { // party
boolean flag = false;
for (int person : parties[i]) { // 참석자
if(people_know[person]){
flag = true;
break;
}
}
if(!flag) result++;
}
System.out.println(result);
}
public static int find(int idx) {
if(parent[idx]==idx){
return idx;
}
parent[idx] = find(parent[idx]);
return parent[idx];
}
public static void union(int a, int b) {
int parent_b = find(b);
parent[parent_b] = a; // b의 parent를 a로 변경
}
}
✔ 알고리즘 분류 - 그래프 이론, 자료 구조, 그래프 탐색, 분리 집합
✔ 난이도 - 🟡 Gold 4
딱히없음