[백준 1043번] 거짓말 - java

문제 설명

1. 사람 수, 파티의 수가 첫 줄에 주어지고

2. 둘쨰 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다.

3. 그 다음부터는 파티의 갯수만큼 사람들이랑 그 사람의 번호가 주어진다.

4. 진실을 아는 사람이 속한 파티나, 그 사람이랑 같은 파티에 한번이라도 참가한 사람이 있거나, 같은 파티에 참석한 점이 있는 사람이 한명이라도 있는 파티에서는 거짓말을 못한다.

5. 거짓말 할 수 있는 파티 수를 구하면 된다.

 

풀이 과정

 1. 유니온 파운드 문제이다.

 2. 모든 사람의 관계를 조사해서, 진실을 아는 사람이 같은 유니온에 들어가있는지 파악하면 된다.

 3. 사실 그렇게 어려운 문제는 아니겠지만(아니겠지?) 유니온 파인드에 관한 지식은 가지고 있어야 풀 수 있다. 한번 브루트포스로 풀어보려 했더니 당연하게도 시간초과가 났음ㅇㅇ

 4. 아래 코드에서 중요하게 보아야 하는 점은 find 와 union 이다. 말하자면 두 선이 연결되어 있는지를 보려면 근본적으로 어디서부터 시작하는지를 알면 된다는 것이다.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static int[] parent;

    // 지금 이녀석의 맨 위 도착점(기준점) 을 찾는다.
    public static int find(int x) {
        if (x == parent[x]) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    // x를 기준으로 두 선의 루트를 맞춰준다.
    public static void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
        }
    }

    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 num = Integer.parseInt(st.nextToken()); // 진실을 아는 사람 수

        if (num == 0) {
            System.out.println(M);
            return;
        }

        int[] truth = new int[num];
        for (int i = 0; i < num; i++) {
            truth[i] = Integer.parseInt(st.nextToken());
        }

        // 전체 파티피플들을 보관
        List<List<Integer>> partyList = 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<>();
            // 기준점
            int firstPerson = Integer.parseInt(st.nextToken());
            party.add(firstPerson);

            // 파티에서 만났던 사람들을 묶어준다
            for (int j = 1; j < cnt; j++) {
                int person = Integer.parseInt(st.nextToken());
                party.add(person);
                union(firstPerson, person); // 파티에 속한 사람들끼리 연결
            }
            partyList.add(party);
        }

        // 진실을 아는 사람들을 모두 같은 그룹으로 묶음
        for (int i = 1; i < truth.length; i++) {
            union(truth[0], truth[i]);
        }

        // 거짓말을 할 수 있는 파티 개수 계산
        int ans = 0;
        for (List<Integer> party : partyList) {
            boolean canLie = true;
            for (int person : party) {
                if (find(person) == find(truth[0])) {
                    canLie = false;
                    break;
                }
            }
            if (canLie) {
                ans++;
            }
        }

        System.out.println(ans);
    }
}