백준 1043 거짓말 - JAVA

1043 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

import java.io.*;
import java.util.*;
 
public class Main {
    static int[] parent;
    static int find(int x) {
        if(parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }
    static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            parent[rootB] = rootA;
        } 
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        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+1; i++) {
            parent[i] = i;
        }
        List<Integer>[] parties = new ArrayList[M];
        for (int i = 0; i < M; i++) {
            parties[i] = new ArrayList<>();
        } 
        
        st = new StringTokenizer(br.readLine());
        int num = Integer.parseInt(st.nextToken());
        List<Integer> truth = new ArrayList<>();
        for (int i = 0; i < num; i++) {
            truth.add(Integer.parseInt(st.nextToken()));
        } 
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int participate = Integer.parseInt(st.nextToken());
            for (int j = 0; j < participate; j++) {
                parties[i].add(Integer.parseInt(st.nextToken()));
            } 
            for (int j = 0; j < parties[i].size(); j++) {
                union(parties[i].get(0), parties[i].get(j));
            } 
        }
        
        Set<Integer> truthRoot = new HashSet<>();
        for(int t : truth) {
            truthRoot.add(find(t));
        }
        int result = 0;
        for (List<Integer> party : parties) {
            boolean lieParty = true;
            for(int i : party) {
                if (truthRoot.contains(find(i))) {
                    lieParty = false;
                    break;
                }
            }
            if (lieParty) {
                result++;
            }
        } 
        bw.write(String.valueOf(result));
        bw.flush();
    }
}

 

알고리즘 설명

---

해당 문제는 Union find라는 자료구조를 정확히 이해하고 있다면 식은 죽 먹기 수준의 문제였다고 생각합니다. 하지만 상대적으로 흔한 자료구조는 아니기에 이번 문제를 통해 정확히 이해하고 가는 것만큼 중요한 것은 없다고 생각합니다. Union find의 개념은 기본적으로 서로 다른 집합을 합치는 연산(Union), 원소가 어떠한 집합에 속해있는지 찾는 연산(Find)을 지원하기 때문에 Union find라는 이름이 붙었습니다. 먼저 Union find 자료구조가 왜 존재하는지가 중요할텐데요, Union find는 각각의 두 노드가 서로 연결되어있는지 확인하고, 두 노드를 연결하는 작업을 효율적으로 실행하기 위해 존재합니다. 앞서 말씀드린 것처럼 Union find는 원소가 어떤 집합에 속하는지 Find하고, 주어진 조건에 따라 Union하는 작업입니다. 동작방식을 더 자세하게 말씀드리면, 먼저 각 원소를 자신만 포함되어있는 그룹으로 각각 나누어 줍니다. 이후 합쳐야 하는 그룹이 있다면, 가장 작은 원소를 대표원소(루트 노드)로 정한 이후 그룹을 합칩니다.

예를 들어 { 0, 1 }, { 3, 4 } 이 네 그룹의 각 원소가 대표원소이고, 모든 그룹을 합친다고 가정한다면 네 그룹 중 0이 가장 작은 원소이기 때문에, 0을 대표원소로 정하고 그룹은 {0, 1, 3, 4}와 같이 하나로 합쳐지는 것입니다. 가장 중요한 것은 아래 그림과 같이 모든 원소가 재귀적으로 find()함수를 거쳤을 때, 대표원소를 가리켜야 한다는 것입니다.

참고 : Potato Coders 영상 중 일부 캡쳐

하지만 합치는 집합의 개수가 많아지면, 대표 원소를 찾아가는 과정이 길어지기 때문에 경로를 압축하는 과정이 필요합니다. 해당 문제에서는 parent[] 배열로 각 원소의 대표 원소를 저장하고, 그룹을 합치는 경우 parent[] 배열을 업데이트하여 find() 함수를 parent[] 배열과 연결하여 한 번의 사이클에 가리킬 수 있도록 했습니다.

DP 문제를 풀어보신 분들은 DP 문제와 유사한 부분이 있다고 생각하셨을 텐데요, 중복 계산을 줄이기 위해 DP(동적 계획법)에서 사용되는 메모이제이션과 같은 원리라고 보시면 됩니다.

Union-Find에 대해 조금 더 깊이 알고 싶은 분들은 아래에 첨부한 유튜브 영상을 참고 바랍니다.

 

- 참고 -

https://www.youtube.com/watch?v=ayW5B2W9hfo

 

코드 해석

---

find()함수는 각 원소의 대표(루트) 원소를 찾습니다. 메모이제이션을 활용한 경로압축기법을 사용하여 찾을 때마다 경로를 최적화합니다. union()함수는 a와 b가 속한 집합을 합치고, 서로 다른 대표를 가진다면 하나의 대표로 합쳐줍니다.

사람 수(N)과 파티의 개수(M)를 입력받고, 진실을 아는 사람들을 truth라는 리스트에 입력받습니다. 각 파티의 참가자들을 union()함수로하나의 그룹으로 합칩니다. parent[x] = find(parent[x]) 부분에서 각 원소의 대표원소가 parent[] 배열에 저장됩니다.(메모이제이션)

truth리스트의 각 원소를 find()함수를 활용하여 해당 원소가 속한 그룹의 대표원소를 truthRoot에 저장합니다. 어떤 원소인지는 중요하지 않으며, 해당 원소가 진실을 알고 있는 그룹(truthRoot)에 속해 있는지가 핵심입니다. 각 파티의 원소들을 이중 for문으로 순회하면서, 파티에 속한 모든 원소가 진실을 알고 있는 그룹(truthRoot)에 속하지 않은 경우 result 값을 1씩 증가시킵니다. 반복문이 모두 종료되면, 최종적으로 result를 출력합니다.