[백준 13418 : JAVA] 학교 탐방하기 / MST

문제

---

 

 

 

풀이

---

기본 형태의 MST 문제다. 다만, 최소뿐만 아니라 최대 스패닝 트리도 구해야한다는 조건이 추가되었다.

오름차순 우선순위 큐와 내림차순 우선순위 큐 2개에 간선 정보를 담아 해결했다.

 

 

 

코드

---

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

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int N, M;
    private static Queue<Node> ascendQueue = new PriorityQueue<>();
    private static Queue<Node> descendQueue = new PriorityQueue<>((v1, v2) -> v2.weight - v1.weight);
    private static int[] parents;

    static class Node implements Comparable<Node> {
        int v1, v2, weight;

        public Node(int v1, int v2, int weight) {
            this.v1 = v1;
            this.v2 = v2;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o) {
            return weight - o.weight;
        }
    }

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 건물의 수 (=정점의 수)
        M = Integer.parseInt(st.nextToken()); // 도로의 수 (=간선의 수)

        parents = new int[N + 1];

        // 내리막길 가중치는 1, 오르막길 가중치는 K^2
        for (int i = 0; i < M + 1; i++) {
            // 입구와 1번 정점간의 관계가 가장 먼저 주어진다.
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            ascendQueue.add(new Node(v1, v2, weight));
            descendQueue.add(new Node(v1, v2, weight));
        }

        Arrays.fill(parents, -1);
        int edgeCount = 0;
        int maxCost = 0;
        while ((edgeCount <= N) && !ascendQueue.isEmpty()) {
            Node node = ascendQueue.poll();
            if (union(node.v1, node.v2)) {
                edgeCount++;
                maxCost += node.weight;
            }
        }
        maxCost = (N - maxCost) * (N - maxCost); // 비용은 (오르막길 수^2)

        Arrays.fill(parents, -1);
        edgeCount = 0;
        int minCost = 0;
        while ((edgeCount <= N) && !descendQueue.isEmpty()) {
            Node node = descendQueue.poll();
            if (union(node.v1, node.v2)) {
                edgeCount++;
                minCost += node.weight;
            }
        }
        minCost = (N - minCost) * (N - minCost);

        bw.write(maxCost - minCost + "\n");

        bw.flush();
        bw.close();
        br.close();
    }

    private static boolean union(int v1, int v2) {
        v1 = find(v1);
        v2 = find(v2);
        if (v1 != v2) {
            parents[v2] = v1;
            return true;
        }
        return false;
    }

    private static int find(int v) {
        if (parents[v] < 0) return v;
        return parents[v] = find(parents[v]);
    }
}