[BOJ] 23034 조별과제 멈춰! (JAVA)

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

23034번: 조별과제 멈춰!

1. 최소 신장 트리를 만듭니다.

2. X와 Y를 입력받으면, BFS를 이용하여 신장 트리에 사용된 간선 중 X에서 Y까지 가는 간선의 비용의 최댓값을 구합니다.

3. 최소 신장 트리의 비용에서 방금 구한 값을 뺍니다.

 

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

public class Main {
    
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    static int N, M, Q, X, Y, cnt, sum;
    static int[] parent;
    static boolean[] visited;
    static ArrayList<Line>[] lines, used;
    static PriorityQueue<Line> pq = new PriorityQueue<>();

    public static void main(String[] args) throws Exception {

        st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        lines = new ArrayList[N + 1];
        used = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            lines[i] = new ArrayList<>();
            used[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            lines[from].add(new Line(from, to, cost));
            lines[to].add(new Line(to, from, cost));
            pq.add(new Line(from, to, cost));
        }

        make();

        // MST 만들기
        while(!pq.isEmpty()) {
            Line l = pq.poll();
            if(union(l.from, l.to)) {
                used[l.from].add(l);
                used[l.to].add(new Line(l.to, l.from, l.cost));
                sum += l.cost;
                if (++cnt == N - 1) break;
            }
        }

        // 질문 처리
        Q = Integer.parseInt(br.readLine());
        for (int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            X = Integer.parseInt(st.nextToken());
            Y = Integer.parseInt(st.nextToken());
            sb.append(sum - bfs()).append("\n");
        }

        System.out.print(sb.toString());

    }

    static int bfs() {

        visited = new boolean[N + 1];
        Queue<Pos> q = new LinkedList<>();
        visited[X] = true;
        for (Line l : used[X]) {
            q.offer(new Pos(l.to, l.cost));
        }

        while(!q.isEmpty()) {

            Pos p = q.poll();

            if(p.index == Y) return p.max;

            for (Line l : used[p.index]) {
                if(!visited[l.to]) {
                    visited[l.to] = true;
                    q.offer(new Pos(l.to, Math.max(p.max, l.cost)));
                }
            }

        }

        return 0;

    }

    static boolean union(int a, int b) {

        a = find(a);
        b = find(b);

        if(a == b) return false;

        if(a < b) parent[b] = a;
        else parent[a] = b;
        return true;

    }

    static int find(int a) {

        if(parent[a] == a) return a;

        return parent[a] = find(parent[a]);

    }

    static void make() {

        parent = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }

    }

    static class Pos {

        int index, max;

        public Pos (int index, int max) {
            this.index = index;
            this.max = max;
        }

    }

    static class Line implements Comparable<Line> {

        int from, to, cost;

        public Line (int from, int to, int cost) {
            this.from = from;
            this.to = to;
            this.cost = cost;
        }

        @Override
        public int compareTo (Line o) {
            return this.cost - o.cost;
        }

    }

}