[백준] 1043번 - 거짓말 [Java]

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

 

[백준] 1043번 - 거짓말 [Java]

[백준] 1043번 - 거짓말 [Java]

[백준] 1043번 - 거짓말 [Java]

---

1.  아이디어

 

유니온 파인드 알고리즘을 통해 각 파티를 집합으로 표현한 후 각 파티의 그룹장만 따로 담아준다.
이후 각 파티의 그룹장이 진실을 아는 지 판단했다.

---

2. 문제풀이

 

진실을 아는 사람은 부모의 번호를 0번으로 설정했고 파티의 그룹장은 번호가 작은 사람이 오도록 했다.
유니온 파인드 알고리즘을 통해 그룹을 형성한 후 그룹장만 따로 Queue에 담아줬다.
이러면 Queue의 그룹장의 부모(최고 조상)이 0인지 여부로 그룹에 진실을 말해야하는지 간단하게 판단할 수 있다.

---

3. 코드

 

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

public class Main {

    private static int[] p;

    private static int[] make(int N) {
        int[] arr = new int[1 + N];
        for (int i = 1; i <= N; i++) {
            arr[i] = i;
        }
        return arr;
    }

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

    private static void union(int x, int y) {
        if (find(x) < find(y)) p[find(y)] = find(x);
        else p[find(x)] = find(y);
    }

    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());

        p = make(N);

        st = new StringTokenizer(br.readLine());
        st.nextToken();
        while (st.hasMoreTokens()) {
            p[Integer.parseInt(st.nextToken())] = 0;
        }

        Queue<Integer> q = new ArrayDeque<>();
        int cnt = 0;
        for (int i = 0; i < M; i++) {
            PriorityQueue<Integer> pq = new PriorityQueue<>();
            st = new StringTokenizer(br.readLine());
            st.nextToken();

            while (st.hasMoreTokens()) {
                pq.add(Integer.parseInt(st.nextToken()));
            }

            int x = pq.remove();
            q.add(x);

            while (!pq.isEmpty()) {
                union(x, pq.remove());
            }
        }

        while (!q.isEmpty()) {
            int x = q.remove();

            if (find(x) != 0) cnt++;
        }

        System.out.println(cnt);
    }
}

---

4. 후기