백준 23034 - 조별 과제 멈춰!

문제

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

리뷰

크루스칼과 BFS를 활용하여 풀이할 수 있는 문제였다.

먼저 T를 구하기 위해서 우선 주어진 모든 간선에서 MST를 구성하여
모든 정점을 연결하는데 필요한 최소한의 간선만을 남겨야 한다.
이를 위해 간선을 표현하는 Edge 클래스를 바탕으로 간선 데이터들을 비용 기준
최소힙에 저장한 후, 크루스칼을 통해 인접 리스트(List<List<Node>>)의 형태로
MST를 구성하였다.

이후 쿼리를 어떤 식으로 처리할 지가 관건이었는데, 생각을 해보면 MST는 모든
정점을 연결하는데 필요한 최소한의 간선만으로 구성되있으므로 팀장으로 주어진
두 정점을 연결하는 경로상에서 가장 큰 비용을 가지는 간선을 제외해주면 해당
정점들이 팀장일 때 최소한의 T를 도출할 수 있다.

로직의 시간복잡도는 BFS가 MST를 탐색하기에 사실상 $O(N)$의 시간복잡도를 띄고
쿼리를 처리하는 부분에서 $O(QN)$으로 수렴하므로 $Q=10^4$, $N=10^3$인 최악의
경우에도 무난히 제한 조건 2초를 통과할 수 있다.

코드

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

import static java.lang.Integer.*;

public class Main {
    static int[] parent;
    static PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.w));
    static List<List<Node>> mst = new ArrayList<>();

    static boolean[] visited;

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

        parent = new int[N + 1];
        visited = new boolean[N + 1];

        int u, v, w;
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = parseInt(st.nextToken());
            v = parseInt(st.nextToken());
            w = parseInt(st.nextToken());

            pq.offer(new Edge(u, v, w));
        }

        int sum = kruskal(N);
        int Q = parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        while (Q-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = parseInt(st.nextToken());
            v = parseInt(st.nextToken());

            sb.append(sum - bfs(u, v)).append("\n");
        }

        System.out.print(sb);
        br.close();
    }

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

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

    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 kruskal(int N) {
        Arrays.fill(parent, -1);
        mst.add(null);
        for (int i = 0; i < N; i++) mst.add(new ArrayList<>());

        int selected = 0, sum = 0;

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

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

            selected++;
            sum += e.w;
            mst.get(e.u).add(new Node(e.v, e.w));
            mst.get(e.v).add(new Node(e.u, e.w));
        }

        return sum;
    }

    static int bfs(int start, int end) {
        Arrays.fill(visited, false);
        visited[start] = true;

        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(new Node(start, 0));

        while (!queue.isEmpty()) {
            Node cur = queue.poll();

            if (cur.v == end) return cur.d;

            for (Node next : mst.get(cur.v)) {
                if (visited[next.v]) continue;

                visited[next.v] = true;
                queue.offer(new Node(next.v, Math.max(cur.d, next.d)));
            }
        }

        return -1;
    }

    static class Edge {
        int u, v;
        int w;

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

    static class Node {
        int v, d;

        public Node(int v, int d) {
            this.v = v;
            this.d = d;
        }
    }
}

결과