[코드트리 조별과제] HashSet 활용

해시 셋은 보통 중복을 제거하여 고유의 값을 뽑아낼때 사용한다. 

 

약간 돌려서 얘기하자면, 쓸데없는 값이 중복되어 연산되는걸 막아줄때 사용하기도 한다.

 

코드트리에 있는 "초대장과 번호표" 라는 문제가 있는데, 이는 백준의 "거짓말" 과 비슷하게 생겼다.

 

물론 백준의 "거짓말" 문제는 범위가 매우 작다( 코드트리 문제 기준으로 그룹이 50개고 각 그룹별 50명이다. )

 

하지만 코드트리의 문제는 범위가 그룹은 최대 25만개에 인원또한 25만명으로 책정되어 있다.

 

이걸로 인해 시간복잡도 N^2의 완전탐색은 불가하다고 생각하겠지만

 

중요한 조건이 추가적으로 있다.

 

바로 " 모든 그룹 내 사람 수의 총합 <= 250,000 " 이란 것이다. 

 

이걸 해석해보면 그룹이 극단적으로 25만개 였다 하더라도, 그룹별 인원은 1명이 되는것이다.

 

즉, 그룹과 인원이 상대적으로 존재하게 되는것이고, 이는 그룹별로 인원을 순회하는데 있어서 시간복잡도를 크게 염려하지 않아도 되는 부분이다.

 

-> 이 시점에서 완탐이 가능하단걸 알아야 한다.

 

또한 추가적으로 사람의 번호표를 나타내는 N이란 숫자가 있는데, 이는 사람수보다 많다. 즉, 중복된 사람들이 그룹별로 상당수 존재한단 의미가 되고,

 

문제에서 원하는 초대장을 받는 인원수를 구하는데에 있어서 중복을 제거해야 함과 동시에, 중복을 제거함으로서 얻는 시간복잡도 적 이득이 있다는것

 

그럼 문제로 다시 돌아가서 초기 초대장을 받은 인원의 번호를 주고, 각 그룹별로 인원이 K명일때 K-1명까지 초대장을 받았다면 나머지 한명도 초대장을 받은걸로 한다 라고 되어있다.

 

즉, 어떤 번호에 대해서 초대장을 부여한다면, 해당 번호를 가진 모든 그룹에 영향을 줄 수 있다는것이 된다.

 

또한, 다음에 해당 번호에 대해서 고려하게 됬을때, 해당번호는 이미 초대장을 받아갔어요 라는것을 인지하기도 해야하고

 

해당 그룹들은 이미 해당 번호에 대해서 처리가 되었어요도 남겨야 한다. 즉, 그룹별로 번호별 삭제연산도 필요하다.

 

그래서 어떤 번호 N을 가진 사람에게 초대장을 건낸다는것은 그 N이 속해있는 모든 그룹 Gi에 대하여 영향을 주고

 

그 영향에 대한 처리에 있어서 그룹별 Gi 에 대해서 어떤 번호들이 있는지 list(N) 이 필요하다.

 

결과적으로: N에 대한 G를 저장할 자료구조와 G에 대한 N을 저장할 자료구조가 필요하다. (역 인덱싱)

 

그리고 각 N을 노드로 생각해봤을때, 어떤 노드와 다른 노드들은 연결되어 있는 형태 즉, 그래프로 해석할 수 있다.

 

따라서 완전탐색 기법 중 인접한 노드들 모두를 먼저 탐색하는 BFS를 사용하여 완전탐색을 실행한다.

 

import java.util.*;
import java.io.*;
import java.util.function.Function;

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

public class Main {
    static int n;
    static int g;
    static HashSet<Integer> [] groups;
    static ArrayList<Integer> [] pToG; // 어떤 사람 기준으로 모든 그룹의 번호 저장
    static boolean [] v;
    static StringTokenizer stk;
    static int ans;
    public static void main(String[] args) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        stk = new StringTokenizer(bf.readLine());
        n = Integer.parseInt(stk.nextToken());
        g = Integer.parseInt(stk.nextToken());
        groups = new HashSet[g+1];
        pToG = new ArrayList[n+1];
        for(int i = 1;i<g+1;i++){
            groups[i] = new HashSet<>();
        }
        for(int i = 1;i<n+1;i++){
            pToG[i] = new ArrayList<>();
        }
        for(int i = 1;i<g+1;i++){
            stk = new StringTokenizer(bf.readLine());
            int size = Integer.parseInt(stk.nextToken());
            for(int j = 0;j<size;j++){
                int peopleNumber = Integer.parseInt(stk.nextToken());
                groups[i].add(peopleNumber);
                pToG[peopleNumber].add(i);
            }
        }
        ans = 0;
        v = new boolean[n+1];
        v[1] = true;
        go(1);
        System.out.println(ans);


    }
    static void go(int start){
        Queue<Integer> queue =new ArrayDeque<>();
        queue.add(start);
        while(!queue.isEmpty()){
            int nowPeopleNumber = queue.poll();
            ans++;
            for(int i = 0;i<pToG[nowPeopleNumber].size();i++){
                // 이 사람이 속해있는 모든 그룹에 해당 번호를 지워야 한다.
                int gNumber = pToG[nowPeopleNumber].get(i);
                groups[gNumber].remove(nowPeopleNumber);
                if(groups[gNumber].size() == 1){
                    for(Integer last: groups[gNumber]){
                        // 중복연산이 일어나지 않도록 해야하는데
                        // 이유는 사이즈가 1남은 것들을 마저 제거하지 않기 때문이다.
                        if(v[last]) continue;
                        v[last] = true;
                        queue.add(last);
                        
                    }
                }
            }
            
        }
    }
}