[BOJ/Graph] 백준 1043 - 거짓말 (Java)

백준 1043 - 거짓말

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

문제

파티에서 이야기를 말할 때, 있는 그대로 말하거나 과장해서 말함
거짓말쟁이로 알려지기 싫기 때문에 진실을 아는 사람이 파티에 오면 진실을 이야기 함
어떤 사람이 파티에서 진실을 듣고, 또 다른 파티에서 과장된 이야기를 들으면 거짓말쟁이로 알려짐

입력
첫째 줄: 사람 수 N, 파티 수 M (1 <= N, M <= 50)
둘째 줄: 이야기의 진실 아는 사람 수와 번호 (0 <= 진실 아는 사람 수 <= 50)
(진실을 아는 사람 수 먼저 주어지고 그 개수만큼 사람들 번호(1 ~ N) 주어짐)
셋째 줄 ~ M개 줄: 각 파티마다 오는 사람 수, 번호 (1 <= 각 파티마다 오는 사람 수 <= 50)
출력: 거짓말쟁이로 알려지지 않으면서 과장된 이야기를 할 수 있는 파티 개수의 최댓값

---

풀이

Union-Find (같은 파티 참석 -> 같은 그룹) 

for (int i = 0; i < M; i++) {
    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);

    // 파티의 모든 사람을 하나의 그룹으로 묶기
    for (int j = 0; j < cnt - 1; j++) {
        union(party.get(j), party.get(j + 1));
    }
}

 

진실을 아는 사람 루트 저장

Set<Integer> truthRoots = new HashSet<>();
for (int x : truthPeople) {
    truthRoots.add(find(x));
}

---

코드

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

// 거짓말
public class boj_1043 {
    static int N, M;
    static int[] unf;
    static List<Integer> truthPeople;
    static List<List<Integer>> parties;

    static int find(int v) {
        if (v == unf[v]) return v;
        return unf[v] = find(unf[v]);
    }

    static void union(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if (fa != fb) unf[fb] = fa;
    }

    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());

        unf = new int[N + 1];
        for (int i = 1; i <= N; i++) unf[i] = i;

        st = new StringTokenizer(br.readLine());
        int t = Integer.parseInt(st.nextToken());
        truthPeople = new ArrayList<>();

        for (int i = 0; i < t; i++) {
            truthPeople.add(Integer.parseInt(st.nextToken()));
        }

        parties = 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);

            for (int j = 0; j < cnt - 1; j++) {
                union(party.get(j), party.get(j + 1));
            }
        }

        if (truthPeople.isEmpty()) {
            System.out.println(M);
            return;
        }

        Set<Integer> truthRoots = new HashSet<>();
        for (int x : truthPeople) {
            truthRoots.add(find(x));
        }

        int ans = 0;
        for (List<Integer> party : parties) {
            boolean flag = true;

            for (int p : party) {
                if (truthRoots.contains(find(p))) {
                    flag = false;
                    break;
                }
            }

            if (flag) ans++;
        }

        System.out.println(ans);
    }
}