[Baekjoon Online Judge] 1043. 거짓말 // 해설 (Java)

https://www.acmicpc.net/problem/1043

 

문제

 

---

해설

파티에 진실을 아는 사람이 있다면 반드시 진실을 말해야 하고 그 파티에 함께 있는 사람도 진실을 아는 사람이 되는 아주 현실적인 상황이라 문제를 해석하는 것은 어렵지 않습니다.

다만 주의할 점은 파티에서 거짓말을 한 뒤에 참여자가 진실을 아는 사람이 되는 상황도 있어서는 안 된다는 것입니다.

따라서 핵심은 모든 파티가 끝났을 때를 기준으로 진실을 아는 사람을 골라내고, 진실을 아는 사람이 포함되지 않은 파티의 수를 세면 된다는 것

 

입력의 크기가 워낙 작아서 Brute-force를 포함해 아마 다양한 방법으로 풀 수 있을 것 같습니다. (귀찮아서 풀어보지는 않음) 하지만 그러면 시뮬레이션 유형에 가까워지고 구현이 더 복잡해질 것 같네요.

 

저는 Set, Union-Find 두 자료구조로 풀면 속도도 빠르고 간단하게 코드를 작성할 수 있을 것 같았고 최종적으로 Union-Find를 사용해서 풀었습니다.

 

시간복잡도는 최악의 경우 O(NM) (모든 파티에 모든 사람이 참여)

---

구현

Code (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {

    static int[] parent, rank;
    final static int ME = 0;

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

        int N = Integer.parseInt(st.nextToken()); // num of people
        int M = Integer.parseInt(st.nextToken()); // num of parties

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

        int truthKnowerCount = Integer.parseInt(st.nextToken());
        if (truthKnowerCount == 0) {
            System.out.println(M);
            return;
        }

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

        for (int i = 0; i < truthKnowerCount; i++) {
            int truthKnower = Integer.parseInt(st.nextToken());
            unionSet(ME, truthKnower);
        }

        int[][] parties = new int[M][]; // 파티별 참가자 기록
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int participantsCount = Integer.parseInt(st.nextToken());
            parties[i] = new int[participantsCount];
            parties[i][0] = Integer.parseInt(st.nextToken()); // 첫 참가자 기록

            // 나머지 참가자들을 첫 참가자와 Union
            for (int j = 1; j < participantsCount; j++) {
                parties[i][j] = Integer.parseInt(st.nextToken());
                unionSet(parties[i][0], parties[i][j]);
            }
        }

        int ans = M;

        for (int i = 0; i < M; i++) {
            for (int participant : parties[i]) {
                if (findSet(participant) == findSet(ME)) {
                    ans--;
                    break;
                }
            }
        }

        System.out.println(ans);
    }

    static void unionSet(int u, int v) {
        int root1 = findSet(u);
        int root2 = findSet(v);
        if (root1 != root2) {
            if (rank[root1] < rank[root2]) {
                parent[root1] = root2;
            } else if (rank[root1] > rank[root2]) {
                parent[root2] = root1;
            } else {
                parent[root2] = root1;
                rank[root1]++;
            }
        }
    }

    static int findSet(int v) {
        if (v == parent[v]) {
            return v;
        }
        return parent[v] = findSet(parent[v]);
    }
}