[Java/Union-find] 백준 1043. 거짓말

🤔 Intuition

처음에 완탐인 줄 알았다. N과 M이 50 이하이고 시간제한이 2초 이내라서 거의 확신을 했다.

근데, 일단 TC만 맞고 나서, 제출하니까 3%에서 바로 틀렸다. (실전이였다면 맞았다고 착각해서 틀렸을 확률 99.9%)

 

진실을 아는 사람들이 있는 파티에 참여하는 사람들도 진실을 알게 되는데, 이게 1다리만 계산하면 되는 게 아니라 엮이는 사람 간의 관계 모양이 skewed tree가 될 경우에는 반복수를 감안할 수 없기 때문에 브루트포스로는 반복수의 기준이 명확하지 않다.

 

즉, 관계성을 계속 저장해둬야 하는 문제였던 거다. 이는 사람간의 그래프를 형성하는 문제라고 볼 수 있으므로, union find로 풀어낼 수 있다.

🔎 Algorithm & Complexity

* @algorithm union-find
* @time O(logN) : union-find -> 132ms
* @memory O(N*M) : parent 배열 * M 크기의 list

👨🏻‍💻 Logic

단순하다.

1. 진실을 아는 사람들은 0번 노드를 root 노드로 갖도록 설정한다.
2. 모든 사람들의 부모 노드를 union시킨다.
3. 결과적으로, 진실을 아는 사람들과 한번이라도 만난 사람들은 0번 노드를 루트 노드로 갖게 되지만, 진실을 아는 사람과 한번도 만나지 못한 사람들은 0이 아닌 노드를 루트 노드로 갖게 된다.
4. 따라서, 마지막에 파티를 순회하면서, 사람들 한명만 체크해도 진실을 알게 된 사람들이 구성된 파티인지 아닌지 카운트가 가능하므로, 이를 이용해 "M개의 파티 - 진실을 아는 사람들이 있는 파티 개수"로 답을 구할 수 있다.

public class BOJ_1043_거짓말 {
    private static int[] parent;
    private static int N, M;
    private static List<Integer>[] parties;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());

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

        // 0을 root로 두는 건 진실은 아는 것.
        st = new StringTokenizer(br.readLine());
        int cnt = Integer.parseInt(st.nextToken());
        if (cnt > 0) {
            for (int i = 0; i < cnt; i++) {
                int v = Integer.parseInt(st.nextToken());
                union(0, v);
            }
        }

        for (int i = 0; i < M; i++) {
            parties[i] = new ArrayList<>();
            st = new StringTokenizer(br.readLine());
            cnt = Integer.parseInt(st.nextToken());
            int u = 0;
            for (int j = 0; j < cnt; j++) {
                int v = Integer.parseInt(st.nextToken());
                parties[i].add(v);
                if (j == 0) {
                    u = v;
                    continue;
                }
                union(u, v);
            }
        }
        int ans = M;
        int res = 0;
        top:
        for (List<Integer> party : parties) {
            for (Integer i : party) {
                if (find(i) == 0) {
                    res++;
                    continue top;
                }
            }
        }
        sb.append(ans - res);

        br.close();
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static void union(int u, int v) {
        int uRoot = find(u);
        int vRoot = find(v);
        if (uRoot == vRoot) {
            return;
        }
        if (uRoot < vRoot) {
            parent[vRoot] = uRoot;
        } else {
            parent[uRoot] = vRoot;
        }
    }

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