[백준 1043] - 거짓말 Java

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

1043번: 거짓말

풀이

지문 내용 중

당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고,또 다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다.

이야기의 '진실을 아는 사람'들의 집합 A가 있을 때,

A와 함께 파티를 하는 사람들도 이야기의 ‘진실을 아는 사람’이 된다.

예시

진실을 아는 사람들 = {a,b,c}

모르는 사람 = {d,e}

파티 1 = {a, d}

파티 2 = {d, e}

 

위 예시의 경우, a와의 파티 1로 d는 진실을 알게 되었고, 파티 2를 통해 e도 진실을 알게 된다.

 

파티를 함께 하는 사람들끼리 그래프를 연결하여 탐색하면 관계를 모두 표현할 수 있지만,

어떤 사람들끼리 관계가 있는지의 정보는 상대적으로 불필요하기에

 

단순히 같은 집합에 포함된다는 정보를 표현할 수 있는 union-find를 통해 해결하고자 하였다.

 

구현

먼저 진실을 아는 사람들에 대한 정보를 HashSet에 저장한다.

HashSet<Integer> know = new HashSet<>();
int knowNumbers = Integer.parseInt(st.nextToken());
for (int i = 0; i < knowNumbers; i++) {
    know.add(Integer.parseInt(st.nextToken()));
}

 

같은 파티에 참가한 사람들은 같은 집합에 속한다는 처리를 해준다. 

파티의 참가자가 단 1명이라면, union 할 필요가 없어진다.

따라서 참가자가 2명 이상일 때만 union을 수행하는 코드를 작성했다.

for(int i = 1;i<=M;i++) {
    st = new StringTokenizer(br.readLine());
        //참가자 수
    int participants = Integer.parseInt(st.nextToken());
    int a= -1;
        //첫 번째 참가자를 list에 넣음 (연결이 완료된 이후 확인하기 위함)
    a = Integer.parseInt(st.nextToken());
    list.add(a);

        //두 번째 참가자부터 존재하는 경우에만 union을 추가로 수행함
        //같은 파티에 있었기 때문에 첫 번째 참가자 union만해도 같은 파티에 참여한 것을 표현할 수 있다
    for (int j = 1; j < participants; j++) {
        int temp = Integer.parseInt(st.nextToken());
        union(a, temp);
    }
}

이제 파티 참가자들 사이에 같은 집합 안에 존재한다.

 

이제 진실을 아는 사람들의 부모에 대한 집합을 새롭게 다시 HashSet에 저장해 준다.

know = know.stream()
            .map(i -> find(i))
            .collect(Collectors.toCollection(HashSet::new));

stream을 통해 각 i에 대해 find 함수로 부모를 찾아주어 HashSet에 저장했다.

이제 know안에는 진실을 아는 사람들의 집합의 부모가 들어가 있다.

따라서 파티별로 한 명만 골라서 know 집합에 존재하는지 확인하면 이야기할 수 있는 파티의 수가 나온다.

int sum = 0;
for (int i = 0; i < M; i++) {
    if (!know.contains(find(list.get(i)))) {
        sum++;
    }
}
System.out.println(sum);

제출 코드

package 백준_2024년.백준_1월_1주;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class baekjoon1043_거짓말 {

    static void union(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if(fa>fb) {
            parent[fb] = fa;
        }
        else {
            parent[fa] = fb;
        }
    }
    
    static int find (int v) {
        if(parent[v] == v) {
            return v;
        }
        parent[v] = find(parent[v]);
        return parent[v];
    }
    
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        ArrayList<Integer> list = new ArrayList<>();
        int N = Integer.parseInt(st.nextToken());
        parent = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }
        int M = Integer.parseInt(st.nextToken());

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

        for(int i = 1;i<=M;i++) {
            st = new StringTokenizer(br.readLine());
            int participants = Integer.parseInt(st.nextToken());
            int a= -1;
            a = Integer.parseInt(st.nextToken());
            list.add(a);

            for (int j = 1; j < participants; j++) {
                int temp = Integer.parseInt(st.nextToken());
                union(a, temp);
            }
        }

        know = know.stream().map(i -> find(i)).collect(Collectors.toCollection(HashSet::new));

        int sum = 0;
        for (int i = 0; i < M; i++) {
            if (!know.contains(find(list.get(i)))) {
                sum++;
            }
        }
        System.out.println(sum);
    }
}