BOJ_1043 : 거짓말

 

👉 문제링크

1043번: 거짓말

---

---

🔸 문제 분석 🔸

• 문제 내용
  • N명의 사람과 M개의 파티가 있다.
  • 진실을 아는 사람이 참여한 파티에서는 진실만 말해야 한다.
  • 진실을 말한 파티에 있던 사람들도 진실을 아는 사람이 된다.
  • 거짓을 말할 수 있는 파티의 수를 출력한다.
• 풀이 전략
  • 같은 파티 참가자를 연결해야 한다.
  • 각 파티별 참가자 List와 개인 별 참가 파티 List를 만든다.
  • BFS로 진실을 말한 파티와 진실을 알게된 사람들을 추가해 나간다.
  • 진실을 말하지 않은 파티의 수를 출력한다.
• 2024.04.22 추가
  • 기존에 BFS를 통해 풀이했지만, 분리 집합으로도 풀이할 수 있어서 다시 풀어보았다.
  • 같은 파티에 참가한 인원들을 union 연산으로 같은 집합에 넣어준다.
  • 파티의 집합에 진실을 아는 사람들이 포함되어 있지 않으면 카운트한다.

🔸 코드 🔸

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        ArrayList<Integer>[] person = new ArrayList[N + 1];
        ArrayList<Integer>[] party = new ArrayList[M];
        Boolean[] know = new Boolean[N + 1];
        Boolean[] visited = new Boolean[M];

        for (int i = 1; i <= N; i++) {
            person[i] = new ArrayList<>();
            know[i] = false;
        }

        for (int i = 0; i < M; i++) {
            party[i] = new ArrayList<>();
            visited[i] = false;
        }

        for (int i = 0; i < M; i++) {
            StringTokenizer st1 = new StringTokenizer(br.readLine());
            int person_cnt = Integer.parseInt(st1.nextToken());
            for (int j = 0; j < person_cnt; j++) {
                int ps = Integer.parseInt(st1.nextToken());
                party[i].add(ps); // 파티 별 참가자 기록
                person[ps].add(i); // 개인 별 참가 파티 기록
            }
        }

        // BFS
        int cnt = M;
        Queue<Integer> que = new ArrayDeque<>();

        // 처음 부터 진실을 아는 사람들 큐 초기화
        int know_cnt = Integer.parseInt(st.nextToken());
        for (int i = 0; i < know_cnt; i++) {
            int k = Integer.parseInt(st.nextToken());
            know[k] = true;
            que.add(k);
        }

        while (!que.isEmpty()) {
            int np = que.poll();
            for (int pt : person[np]) {
                if (!visited[pt]) {
                    visited[pt] = true;
                    cnt--;
                    for (int ps : party[pt]) {
                        if (!know[ps]) {
                            know[ps] = true;
                            que.add(ps);
                        }
                    }
                }
            }
        }

        // Output
        bw.write(Integer.toString(cnt));
        bw.flush();
    }
}

🔸 코드 해석 🔸

• 개인 별 참가한 파티 번호, 파티 별 참가자 번호를 ArrayList에 입력받는다.
• 처음부터 진실을 아는 사람들은 큐의 초기값으로 넣는다.
  • 진실을 아는 사람 명단 know 배열을 true로 바꾼다.
• 큐가 빌 때까지 반복하며 진실을 아는 사람들을 추가한다.
  • 현재 참가자가 참여한 파티 목록을 순회한다.
  • 아직 거짓 파티였으면, 진실을 들었으므로 visited를 true로 바꾸고,
    거짓 파티의 수 cnt를 -1한다.
  • 해당 파티에 소속 된 참가자들 중 진실을 알게된 사람들을 큐에 넣고 know는 true로 바꿔준다.
• cnt를 출력한다.

 

🔸 분리 집합 코드 🔸

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    private static int[] parent;

    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int known = Integer.parseInt(st.nextToken());

        if (known == 0) {
            bw.write(Integer.toString(M));
            bw.flush();
            return;
        }

        parent = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }

        // Disjoint Set

        int[] knowns = new int[known]; // 사실을 아는 사람들
        ArrayList<Integer>[] list = new ArrayList[M];

        for (int i = 0; i < known; i++) {
            knowns[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < M; i++) {
            list[i] = new ArrayList<>();
            st = new StringTokenizer(br.readLine());

            int people = Integer.parseInt(st.nextToken());

            int first = Integer.parseInt(st.nextToken());
            list[i].add(first);
            first = find(first);

            for (int j = 1; j < people; j++) {
                int member = Integer.parseInt(st.nextToken());
                list[i].add(member);
                union(first, member);
            }
        }

        int cnt = 0;
        for (int i = 0; i < M; i++) {
            boolean flag = true;
            int pp = find(list[i].get(0));
            for (int j = 0; j < known; j++) {
                if (find(pp) == find(knowns[j])) {
                    flag = false;
                    break;
                }
            }
            if (flag) cnt++;
        }

        // Output
        bw.write(Integer.toString(cnt));
        bw.flush();
    }

    private static void union(int a, int b) {
        int ap = find(a);
        int bp = find(b);

        if (ap != bp) parent[ap] = bp;
    }

    private static int find(int a) {
        if (parent[a] == a) return a;
        return parent[a] = find(parent[a]);
    }
}

---

🔸 end 🔸

• 소속(연결) 정보를 ArrayList로 저장한 뒤 BFS를 통해 쉽게 풀이할 수 있었다.
• 문제 태그에 분리 집합(Disjoint Set) 이 있길래 해당 풀이를 찾아보았다. (참고 포스팅)
  • 연결 되어 있는 참가자들을 같은 집합에 포함되어있다고 보고, 집합의 한 원소가 진실을 알게 되면 해당 집합 모두 진슬을 아는 방식의 풀이었다.
  • 일반적인 Union-Find와 다르게, 집합 내 원소 모두 진실을 알게 되는지 확인이 필요했고, 거짓 파티의 카운트가 필요해서 추가적인 아이디어가 필요한 것 같다.
• 문제 분석과 풀이 계획을 적어가며 풀이했다.