문제 설명
지민이가 파티 M개에 참여할거다. 가서 거짓말을 하고싶다.
파티M개를 통틀어서 참여하는 사람의 수는 N명이다.
근데 이 N명 중 그 거짓말에 대한 진실을 처음부터 아는 사람들이 존재한다. 각 사람마다 M개의 파티중 여러개의 파티에 참여가능하다.
진실을 아는 사람들이 있는 파티에서는 지민이는 거짓말을 못한다. => 이는 곧 진실을 들은 사람들이 있는 파티에서 거짓말을 못한다는 것을 의미한다.
접근
시간제한은 2초에 N과 M도 50 이하였고 N의 3승을 생각해봐도 브루트포스로 풀리는 문제였다. 처음에 너무 단순하게 생각해서 그냥 맨 처음 진실을 알던 사람들이 참여하는 파티와, 그 파티들에 참여하는 사람들이 참여하는 파티, 까지만 제거하면 된다고 생각했다.
결국 틀렸고 다시 문제를 천천히 읽어보았다.
생각해보니 진실을 아는 사람들은 갈수록 계속 늘어나는 구조였다. 이전풀이에서는 이 반복을 한 번밖에 안하고 있었다. 그래서 더이상 새로운 진실을 알게되는 파티가 안나타날때까지 이 최대 50개의 파티에 대해서 계속 반복을 돌자고 생각했다(solution함수의 while문).
또한, benPartys라는 불리언 배열 변수를 둬서 이미 진실을 말해야하는 파티라면 continue;로 넘어가면 사실상 매번 50개의 파티에 대해 조사하는게 아니라, 아직도 진실을 모르는 파티들만 순회하는 셈이다.
=> 근데, 이 풀이가 맞나 다른 사람들의 풀이를 찾아보니 Union-find라는 다른 개념을 사용해서 풀고 있었다. 근데 시간은 매우 빠른편이였으니 문제없는 풀이같다. 그래도 뒤에서 Union-Find라는 개념을 다룰 예정이다.
풀이
import java.util.*;
import java.util.stream.*;
import java.io.*;
public class Main {
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int N = 0;
static int M = 0;
static ArrayList<ArrayList<Integer>> party = new ArrayList<>();
static boolean[] benPeoples = new boolean[N + 1];
static boolean[] benPartys = new boolean[M + 1];
public static void main(String[] args) throws IOException {
int[] inputMN = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
N = inputMN[0];
M = inputMN[1];
benPeoples = new boolean[N + 1];
benPartys = new boolean[M + 1];
for (int i = 0; i < M + 1; i++) party.add(new ArrayList<>());
StringTokenizer st = new StringTokenizer(br.readLine());
int trueKnowSize = Integer.parseInt(st.nextToken());
for (int i = 0; i < trueKnowSize; i++) {
int truePerson = Integer.parseInt(st.nextToken());
benPeoples[truePerson] = true;
}
for (int i = 1; i <= M; i++) {
st = new StringTokenizer(br.readLine());
int peopleSize = Integer.parseInt(st.nextToken());
for (int j = 0; j < peopleSize; j++) {
int peopleNumber = Integer.parseInt(st.nextToken());
party.get(i).add(peopleNumber);
}
}
solution();
int result = 0;
for (int i = 1; i <= M; i++) {
if (!benPartys[i]) result++;
}
System.out.println(result);
}
static void solution() {
while (true) {
int currentBenPartyCount = 0;
for (int i = 1; i <= M; i++) {
if (benPartys[i]) continue;
boolean isContainBenPersons = false;
for (Integer personNumber : party.get(i)) {
if (benPeoples[personNumber]) {
isContainBenPersons = true;
break;
}
}
if (isContainBenPersons) {
benPartys[i] = true;
currentBenPartyCount++;
for (Integer personNumber : party.get(i)) {
benPeoples[personNumber] = true;
}
}
}
if (currentBenPartyCount == 0) {
break;
}
}
}
}
Union-Find 란?
그래프쪽 알고리즘을 공부해본 적이 따로 없어서 매우 약한 편인데, 이 문제가 그 유형 중 하나였던듯 싶다.
동빈나님의 강의 영상을 보고 과거 알고리즘 수업 시간때 배웠던 개념이라는 것을 떠올렸다. 단순하게 설명하자면, 그냥 두 노드가 서로 같은 그래프로 연결되어있느냐? 를 알고 싶을 때 사용하는 것이다.
이때 그래프를 표현하기 위해 트리 구조를 사용한다고 함.
과정
각 노드 별로 자신의 부모 노드를 가리키는 1차원 배열 테이블을 선언한다.
초기화단계에서는 자신의 부모는 자신으로 가리킨다.
Union
이후, 서로 연결되어야 하는 두 노드 a와 b가 주어지면 a와 b의 각각의 부모노드의 부모노드의 부모노드....의 부모노드를 찾는다. 즉, 두 a와 b 노드가 속한 그래프의 루트노드를 찾는다는 것이다. 이 둘이 다르면 끝내면 된다.
각 그래프의 루트노드 중 더 큰 값이 무엇인지 판단한다. 만약 b노드의 루트노드의 부모노드를 a노드의 루트노드로 수정한다.
즉, 합치는 과정에서 가장 중요한 것은 두 그래프를 합치더라도 트리구조를 해치지 않으면서 하나의 그래프로 합치는 것임.
이때, 노드의 루트노드를 찾기 위해 사용되는 함수가 바로 find함수다.
이 함수는 부모노드가 자기 자신일때까지 계속 재귀로 타고 올라가면서, 그 그래프들의 루트가 아닌 다른 모든 노드들을 루트 노드로 수정해나간다.
판단하기
그렇다면, 두 노드(a,b)가 같은 집합에 속하는지(or 같은 그래프에 속하는) 알고 싶다면?
두 노드(a,b)의 부모노드의 부모노드의 부모노드의..... 부모노드를 확인한다. 이 말은 즉 그 그래프의 루트노드를 확인하겠다는 것이다. 다시 돌아와서, a 와 b 노드 각각이 속한 그래프를 대표하는 루트노드를 확인해보았다. 이 두 값이 다르다면 a와 b는 다른 그래프이다.
import java.util.*;
import java.util.stream.*;
import java.io.*;
public class Main {
static int N = 0;
static int M = 0;
static int[] parentTable = new int[N + 1];
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());
parentTable = new int[N + 1];
for (int i = 1; i <= N; i++) {
parentTable[i] = i;
}
st = new StringTokenizer(br.readLine());
int trueKnowSize = Integer.parseInt(st.nextToken());
if (trueKnowSize == 0) {
System.out.println(M);
return;
}
int[] trueKnows = new int[trueKnowSize];
for (int i = 0; i < trueKnowSize; i++) {
trueKnows[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < trueKnowSize - 1; i++) {
unionParent(trueKnows[i], trueKnows[i + 1]);
}
ArrayList<ArrayList<Integer>> party = new ArrayList<>();
for (int i = 0; i < M + 1; i++) party.add(new ArrayList<>());
for (int i = 1; i < M + 1; i++) {
st = new StringTokenizer(br.readLine());
int partySize = Integer.parseInt(st.nextToken());
if (partySize == 0) continue;
int[] partyPeoples = new int[partySize];
for (int j = 0; j < partySize; j++) {
partyPeoples[j] = Integer.parseInt(st.nextToken());
party.get(i).add(partyPeoples[j]);
}
for (int j = 0; j < partySize - 1; j++) {
unionParent(partyPeoples[j], partyPeoples[j + 1]);
}
}
int result = M;
for (int i = 1; i < M + 1; i++) {
for (int j = 0; j < party.get(i).size(); j++) {
if (findIsSameGroup(trueKnows[0], party.get(i).get(j))) {
result--;
break;
}
}
}
System.out.println(result);
}
// find 함수
static int getParent(int x) {
if (parentTable[x] == x) return x;
else return (parentTable[x] = getParent(parentTable[x]));
}
// union 함수
// 두 a,b노드 각각이 속한 그래프의 대표인 루트 노드들끼리 포함 개념을 넣는게 제일 중요한 개념임(트리구조를 해치지 않으면서).
static void unionParent(int a, int b) {
int root_a = getParent(a);
int root_b = getParent(b);
if (root_a != root_b) parentTable[root_a] = root_b;
}
static boolean findIsSameGroup(int a, int b) {
int parent_a = getParent(a);
int parent_b = getParent(b);
return parent_a == parent_b;
}
}
