백준 1043번 거짓말 - Java 분리 집합

ㄱㅓ짓말은 나빠요

 

 

지민이는 거짓말 쟁이야

 

먼저 사람 수와 파티의 수가 주어진다.

진실을 아는 사람들이 주어지고, 이후에 파티에 참가하는 인원이 주어진다.

거짓말을 하려면 해당 파티에 진실을 아는 사람이 없어야 한다.

 

간단한 문제지만 구현을 어떻게 할지 고민이 됐다.

 

먼저 진실을 아는사람이 파티에 존재한다면, 해당 파티에 있는 사람은 모두 진실을 듣게된다.

해당 파티에 진실을 모르고 있던 사람들을 진실을 아는 집단에 추가하여 업데이트한다.

이후 진실을 아는사람이 없는 파티마다 정답에 ++ 해주면 된다.

 

따라서 진실을 아는사람을 큐에 넣고, 각각의 사람에게 어떤 파티를 참여했는지 정리한다.

BFS를 통해 해당파티에 진실을 아는 사람이 있다면 해당 파티에 있는 전원을 진실 집단에 추가한다.

해당 파티를 visited 를 통해 진실된 사람이 있는지 체크해주고 마지막에 체크가 안된 파티의 개수가 answer이 되겠다.

 

해결 프로세스

1. 진실을 아는 사람들의 집단(A)을 hash set으로 정리한다.

2. 해당 사람들을 큐에 넣는다.

3. 입력된 파티를 정리하고, 각각 사람에게 파티 idx를 넣어 정리한다.

4. BFS를 통해 해당 인물이 참여한 파티를 탐색한다.

5. 해당 파티에서 진실을 모르던 인원을 A에 넣어준다.

6. 해당 파티를 boolean을 통해 체크해준다.

7. 모든 탐색을 마치면 진실을 아는 사람과, 진실을 아는 사람이 있던 파티가 정리된다.

8. boolean으로 false인 파티의 개수를 출력하면 정답이다.

 

 

import java.io.*;
import java.util.*;
 
public class Main { // 거짓말
    public static int N, M, T;
 
    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());
 
        Set<Integer> knowTheTruth = new HashSet<>();
        Queue<Integer> que = new LinkedList<>();
 
        st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());
 
        for (int i = 0; i < T; i++) {
            int person = Integer.parseInt(st.nextToken());
            knowTheTruth.add(person);
            que.offer(person);
        }
 
        List<List<Integer>> parties = new ArrayList<>();
        List<List<Integer>> partyMember = new ArrayList<>();
        boolean[] visited = new boolean[M];
 
        for (int i = 0; i <= N; i++) {
            partyMember.add(new ArrayList<>());
        }
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int cnt = Integer.parseInt(st.nextToken());
            List<Integer> party = new ArrayList<>();
            for (int j = 0; j < cnt; j++) {
                int person = Integer.parseInt(st.nextToken());
                party.add(person);
                partyMember.get(person).add(i);
            }
            parties.add(party);
        }
 
        // 진실 리스트 사람이 파티에 있다면
        // 해당 파티의 모든 사람을 진실 리스트에 추가
        while (!que.isEmpty()) {
            int current = que.poll();
            for (int partyIndex : partyMember.get(current)) {
                if (visited[partyIndex]) continue;
                visited[partyIndex] = true;
                for (int member : parties.get(partyIndex)) {
                    if (!knowTheTruth.contains(member)) {
                        knowTheTruth.add(member);
                        que.offer(member);
                    }
                }
            }
        }
 
        int answer = 0;
        // 방문하지 않은 파티라면 == 즉 진실 아는 사람이 없다면
        for (int i = 0; i < M; i++) {
            if (!visited[i]) {
                answer++;
            }
        }
 
        System.out.println(answer);
    }
}
 

 

막상 블로그를 정리하려니 지금 풀이가 더 맘에 들어서 다시 풀었다 호호

 

🔽 기존 풀이법

 

해결 프로세스

1. 진실을 아는 사람들의 집단(A)을 hash set으로 정리한다.

2. 해당 사람들을 큐에 넣는다.

3. 파티에 참여하는 리스트, 각 파티에 참석하는 사람 집합 저장 리스트로 저장

4. BFS를 통해 해당 인물이 참여한 파티를 탐색한다.

5. 해당 파티에서 진실을 모르던 인원을 A에 넣어준다.

6. 모든 파티를 순회하면서 Collections.disjoint 을 활용해 서로소를 체크한다.

7. 서로소라면 진실을 아는 사람이 없는 파티이므로 answer ++ 해준다.

8. answer 출력

 

import java.io.*;
import java.util.*;
 
public class Main { // 거짓말
    public static int N, M, T;
 
    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());
 
        Set<Integer> knowTheTruth = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
 
        st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());
        for (int i = 0; i < T; i++) {
            int person = Integer.parseInt(st.nextToken());
            knowTheTruth.add(person);
            queue.offer(person);  // 진실을 아는 사람들을 큐에 추가
        }
 
        List<List<Integer>> parties = new ArrayList<>();
        List<Set<Integer>> partyMembers = new ArrayList<>();
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int cnt = Integer.parseInt(st.nextToken());
            List<Integer> party = new ArrayList<>();
            for (int j = 0; j < cnt; j++) {
                party.add(Integer.parseInt(st.nextToken()));
            }
            parties.add(party);
            partyMembers.add(new HashSet<>(party));
        }
 
        while (!queue.isEmpty()) {
            int current = queue.poll();
 
            for (Set<Integer> party : partyMembers) {
                if (party.contains(current)) {
                    for (int member : party) {
                        if (!knowTheTruth.contains(member)) {
                            knowTheTruth.add(member);
                            queue.offer(member);
                        }
                    }
                }
            }
        }
 
        int answer = 0;
        for (List<Integer> party : parties) {
            // 해당 파티에서 거짓말 할 수 있다면(서로소) 체크
            if (Collections.disjoint(party, knowTheTruth)) {
                answer++;
            }
        }
 
        System.out.println(answer);
    }
}
 

 

 

지금보니 Union으로 삭슥삭도 되겠다