[백준]1043번. 거짓말(JAVA)

문제

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

---

풀이

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

public class Main {

    static int[] parent;

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

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 사람의 수
        int m = Integer.parseInt(st.nextToken()); // 파티의 수

        parent = new int[n + 1];

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

        st = new StringTokenizer(br.readLine());
        int people = Integer.parseInt(st.nextToken());
        Set<Integer> known = new HashSet<>();
        for (int i = 0; i < people; i++) {
            known.add(Integer.parseInt(st.nextToken()));
        }

        List<List<Integer>> parties = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int partySize = Integer.parseInt(st.nextToken());
            List<Integer> party = new ArrayList<>();
            for (int j = 0; j < partySize; j++) {
                party.add(Integer.parseInt(st.nextToken()));
            }
            for (int j = 1; j < party.size(); j++) {
                union(party.get(0), party.get(j));
            }
            parties.add(party);
        }

        // 진실을 아는 사람들의 루트 찾기 후 임시 리스트에 추가
        Set<Integer> tempKnown = new HashSet<>();
        for (int person : known) {
            tempKnown.add(find(person));  // 임시 집합에 추가
        }

        known.addAll(tempKnown);  // 임시 집합의 값을 한 번에 known에 추가

        int count = 0;

        for (List<Integer> party : parties) {
            boolean canLie = true;
            for (int person : party) {
                if (known.contains(find(person))) {
                    canLie = false;
                    break;
                }
            }
            if (canLie) count++;
        }

        System.out.println(count);
    }

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

    static void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            parent[rootY] = rootX;
        }
    }
}

 

find-union 알고리즘의 존재를 처음 알았다. 문제를 풀고나서 좀 다듬은 코드이다.

 

코드를 정리해보자면 다음과 같다.

먼저, 정답을 알고 있는 사람들의 집합을 만든다.

다음으로, 파티에 참석한 사람들을 하나의 부모를 가지게 묶어준다. 이 때, 파티 하나의 참가자 중 제일 앞 참가자를 기준 노드로 잡고 진행시킨다.

이렇게 하게 되면 union을 통해 하나의 파티에 대한 그룹이 형성된다.

 

만약 제일 앞 참가자의 노드가 다른 그룹에 대한 값을 갖고 있다면? 그 값까지 같이 묶이게 되는 것이다.

 

최종적으로 파티 참가자들을 순회하며 추적한 부모의 값이 진실을 알고 있는 사람인지 보면 되는 것이다.