백준 10749 - Superbull

문제

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

리뷰

크루스칼을 이용해 풀이할 수 있는 간단한 문제였다.

팀마다 고유한 ID가 주어지고 각 팀간 경기를 하였을때 합산 점수는 각 팀의 ID를
$XOR$ 연산하여 구할 수 있다. 경기가 진행될 때마다 한 팀씩 탈락하고 최종 1팀이
남을 때 끝나므로, ID값을 이용해 모든 팀 조합간의 간선을 형성하여 비용 기준
최대힙에 넣은 후, 크루스칼을 통해 MST(Maximum Spanning Tree, MST의 반대)
를 구하여 답을 도출하였다.

로직의 시간복잡도는 간선의 개수가 $M=N\times (N-1)$일 때 크루스칼의
$O(NlogM)$으로 수렴하고, 이는 $N=2,000$인 최악의 경우에도 무난히 제한 조건
1초를 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;

import static java.lang.Integer.parseInt;

public class Main {
    static int N;
    static int[] parent;
    static int[] ids;

    static PriorityQueue<Edge> pq = new PriorityQueue<>((e1, e2) -> Integer.compare(e2.w, e1.w));

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = parseInt(br.readLine());
        parent = new int[N];
        ids = new int[N];

        for (int i = 0; i < ids.length; i++)
            ids[i] = parseInt(br.readLine());

        for (int u = 0; u < N - 1; u++)
            for (int v = u + 1; v < N; v++) {
                pq.offer(new Edge(u, v, ids[u] ^ ids[v]));
            }

        System.out.println(kruskal());
        br.close();
    }

    static long kruskal() {
        Arrays.fill(parent, -1);
        int turn = 0;
        long sum = 0;

        while (!pq.isEmpty() && turn < N - 1) {
            Edge e = pq.poll();

            if (!union(e.u, e.v)) continue;

            turn++;
            sum += e.w;
        }

        return sum;
    }

    static boolean union(int u, int v) {
        int r1 = find(u);
        int r2 = find(v);

        if (r1 == r2) return false;

        if (parent[r1] < parent[r2]) {
            parent[r1] += parent[r2];
            parent[r2] = r1;
        } else {
            parent[r2] += parent[r1];
            parent[r1] = r2;
        }

        return true;
    }

    static int find(int u) {
        if (parent[u] < 0) return u;

        return parent[u] = find(parent[u]);
    }

    static class Edge {
        int u, v, w;

        public Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
    }
}

결과

비용의 범위가 $2^{30}-1$까지 가능하기 때문에 합의 타입을 long으로
설정해주어야 함을 확인했다.