[Do It! 코딩테스트 자바편(김종관)] 문제 052(백준 1043번)

특징

• 각각의 파티에 참석한 사람들을 union연산해서 연결하면 1개의 파티에 있는 모든 사람들은 같은 대표 노드를 바라보게 된다. 이를 모든 파티를 대상으로 반복해서 수행한다.
• 그런 다음, 각 파티의 대표 노드와 진실을 알고 있는 사람들의 각 대표 노드가 동일한지 find연산을 통해 확인한다. 동일하면 과장된 이야기를 할 수 없고, 동일하지 않아야 과장된 이야기를 할 수 있다.

문제

거짓말 (백준: 1043번)

풀이

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int[] parent;
    static ArrayList<Integer>[] party;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }

        int m = sc.nextInt();
        party = new ArrayList[m + 1];

        int knowSize = sc.nextInt();
        int[] knowPeople = new int[knowSize + 1];
        if (knowSize != 0) {
            for (int i = 1; i <= knowSize; i++) {
                knowPeople[i] = sc.nextInt();
            }
        }

        // 파티 데이터 저장하고 각 파티에 참여한 사람들을 한 그룹으로 묶기
        for (int i = 1; i <= m; i++) {
            int partySize = sc.nextInt();
            party[i] = new ArrayList<>();

            for (int j = 0; j < partySize; j++) {
                party[i].add(sc.nextInt());
            }

            if (partySize > 1) {
                for (int j = 0; j < partySize - 1; j++) {
                    union(party[i].get(j), party[i].get(j + 1));
                }
            }
        }

        int cnt = 0;
        for (int i = 1; i <= m; i++) {
            // 파티에 0명 왔을 때 예외 처리
            if (party[i].size() < 1)
                continue;

            boolean isPossible = true;
            int rootOfParty = find(party[i].get(0));
            for (int j = 1; j <= knowSize; j++) {
                if (rootOfParty == find(knowPeople[j])) {
                    isPossible = false;
                    break;
                }
            }
            if (isPossible) {
                cnt++;
            }
        }

        System.out.println(cnt);
        sc.close();
    }

    private static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            parent[rootA] = rootB;
        }
    }

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