저번주에 못한 알고리즘인 분리 집합에 대해서 알아보자

분리집합(Disjoint Set)

서로 중복되지 않는 부분 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조
→ 서로소 집합 이라고도 한다

각각의 집합이 공통 원소를 가지고 있지 않은 집합이다
전체집합 U에 대해, U의 분리집합 A, B 는 아래의 조건을 만족한다

• A, B는 U의 부분 집합
• A, B는 공통 원소를 가지지 않음
• A, B의 합집합은 전체 집합 U이다

이미 존재하는 집합 U에 대해 겹치는 부분이 발생하지 않도록 모든 원소들을 분리한 부분 집합

Union-Find

Union-Find 알고리즘을 이용해서 분리 집합을 구현하고 조작한다

분리 집합을 합치는 연산인 union 연산과 임의의 원소가 어떤 집합에 속하는지 찾는 find 연산을 제공해서 이렇게 불린다고 한다
각 그룹은 트리의 형태로 표시해준다

연산

• make-set(x)
  • 초기화 작업, x를 유일한 원소로 하는 새로운 집합 만들기
• find(x)
  • x가 속한 집합의 대표값(루트 노드) 반환, x가 어떤 집합에 속해 있는지 찾는 연산
• union(x, y)
  • x가 속한 집합과 y가 속한 집합을 합침

어떤건지 느낌은 알았으니 문제를 한 번 풀어보자

백준 1043번 : 거짓말

골드4 문제이다...
그래도 일단 해보자

문제

지민이는 과장해서 말하는걸 좋아함
지민이를 거짓말쟁이로 알고 있는 사람들이 있음
→ 이 사람들에게는 진실만 얘기함
진실을 들은 사람이 과장된 얘기를 듣지 못하게 조심해야함

입력

첫째 줄

• 사람의 수 N, 파티의 수 M → 50이하의 자연수
  둘째 줄
• 진실을 아는 사람의 수 &rarr 0이상 50 이하의 정수, 번호(1~N)
  셋째 줄 ~ M개의 줄
• 각 파티마다 오는 사람의 수 → 1 이상 50 이하의 정수, 번호

출력

과장된 이야기를 할 수 있는 파티 개수의 최댓값

미진이는 귀찮게 사는 것 같다

풀이

union-find 몰랐으면 못 풀었을 것 같다
코테에 union 함수와 find가 주어지지 않을 수 있으니 많이 풀어서 외워야할 것 같다

package baekjun.unionfind;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

public class P1043 {
    static int[] parent;
    static boolean[] truth;

    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());   // 사람의 수
        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 knowCount = Integer.parseInt(st.nextToken());   // 진실을 아는 사람의 수
        truth = new boolean[n + 1];

        for (int i = 0; i < knowCount; i++) {
            int person = Integer.parseInt(st.nextToken());
            truth[person] = true; // 진실을 아는 사람 저장
        }

        List<List<Integer>> parties = new ArrayList<>();    // 파티 정보
        for (int j = 0; j < m; j++) {
            st = new StringTokenizer(br.readLine());
            int partyPeople = Integer.parseInt(st.nextToken());

            List<Integer> party = new ArrayList<>();
            int firstPerson = -1; // 첫 번째 사람 저장

            for (int k = 0; k < partyPeople; k++) {
                int num = Integer.parseInt(st.nextToken());
                party.add(num);

                if (firstPerson == -1) {
                    firstPerson = num; // 첫 번째 사람 선택
                } else {
                    union(firstPerson, num); // 같은 파티 내 사람들은 연결
                }
            }
            parties.add(party);
        }

        Set<Integer> truthRootSet = new HashSet<>();
        for (int i = 1; i <= n; i++) {
            if (truth[i]) {
                truthRootSet.add(find(i)); // 진실을 아는 사람들의 루트 노드
            }
        }

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

            for (int person : party) {
                if (truthRootSet.contains(find(person))) {
                    canLie = false; // 진실을 아는 그룹에 속하면 거짓말 불가
                    break;
                }
            }

            if (canLie) count++;
        }

        System.out.println(count);
    }

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

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

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

        parent[x] = find(parent[x]);
        return parent[x];
    }
}

이 문제는 진실을 아는 사람과 같은 파티에 있는 사람들을 한 그룹으로 묶어야 된다고 생각했다
한 번이라도 같이 있었으면 그 사람들에게 항상 같은 소리를 해야되니 그 사람들을 같은 그룹으로 합쳐준다
다행히도 번호는 이차원 배열이 아니라 고생을 좀 덜 한 것 같다

진실을 아는 사람의 번호를 boolean 배열에 저장을 해준다
그리고 파티 정보를 저장해준다. 이 때 제일 먼저 나온 사람을 기준으로 union-find를 해준다
그럼 루트 노드가 그 사람들이 될 것이다!

그리고 Set을 통해서 truth[]라는 진실을 아는 사람들이 모여있는 배열에서 해당 값들의 루트 노드를 찾아준다 → 이건 루트노드가 해당 값이면 이 사람들에게도 거짓말을 못하니 루트노드를 통해서 같은 파티에 있었는지를 판단해주기 위해 사용한다

그리고 파티를 돌면서 해당 파티에 루트노드가 진실을 아는 사람들과 같은 사람이 한명이라도 있으면 거짓말을 못하므로 해당 기준을 판단해 한 명도 없으면 count를 올려주고 한 명이라도 있으면 진실을 말해야하므로 count를 올려주지 않는다

후기

union-find 문제인걸 알고 있어서 그런지 그렇게 막 어렵지는 않았다!
그래도 좀 더 문제를 풀어봐야 할 것 같다

지민이처럼은 안살아야겠다..