[BOJ 1922, Java] ネットワーク接続

問題リンク

BOJ 1922

分類

グラフ理論、最小スパンニングツリー

説明

はじめに

最近は問題を解くことばかりに追われて、理論をおろそかにしている気がするため、理論を簡単でも整理しつつ、問題の解法を記録しておこうと思う。

MST（minimum spanning tree、最小スパニングツリー）

• スパニングツリーとは？

グラフ内のすべての頂点を含む木を意味する。

• 最小スパンニングツリー

スパンニングツリーの中で、辺の総長が最も短いもの

• 主な特徴

n個の頂点を通る(n - 1)本の辺を持つ 長さを最小限に抑えるため、社内ネットワークの構築などに活用可能

プリムアルゴリズム

• 初期の頂点を1つ選択

• MSTに含まれる頂点に接続された辺のうち、最も短いものを順次選択

• すべての頂点が接続された場合、終了

クルスカルのアルゴリズム

• すべての辺を重み順に並べ替える

• サイクルを形成しない範囲で、辺を順次追加

• すべての頂点が接続された場合、終了

実装コード

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

public class Main {

    // 간선 정보 클래스 선언
    public static class Connection implements Comparable<Connection> {

        private final int cost;
        private final int start;
        private final int end;

        public Connection(int cost, int start, int end) {
            this.cost = cost;
            this.start = start;
            this.end = end;
        }

        // 가중치를 통한 비교
        public int compareTo(Connection other) {
            return this.cost - other.cost;
        }

    }

    // 정점의 집합을 확인하는 함수
    public static int checkUnion(int[] unionInfo, int targetVertex) {

        if (unionInfo[targetVertex] != targetVertex) {
            unionInfo[targetVertex] = checkUnion(unionInfo, unionInfo[targetVertex]);
        }

        return unionInfo[targetVertex];
    }

    // 정점 2개가 집합을 이루는지 확인하는 함수
    public static boolean isUnion(int[] unionInfo, int vertex1, int vertex2) {
        return checkUnion(unionInfo, vertex1) == checkUnion(unionInfo, vertex2);
    }

    // 집합을 합쳐주는 함수
    public static void makeUnion(int[] unionInfo, int vertex1, int vertex2) {

        int group1 = checkUnion(unionInfo, vertex1);
        int group2 = checkUnion(unionInfo, vertex2);

        if (group2 > group1) {
            unionInfo[group2] = group1;
        } else {
            unionInfo[group1] = group2;
        }

    }

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

        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));

        // 정점 및 간선의 갯수 입력
        int vertexNumber = Integer.parseInt(input.readLine());
        int edgeNumber = Integer.parseInt(input.readLine());

        // 간선 정보를 담을 우선순위 큐 선언
        PriorityQueue<Connection> costPriorityQueue = new PriorityQueue<>();

        // 간선 정보 입력
        for (int i = 0; i < edgeNumber; i++) {
            StringTokenizer connectionInfo = new StringTokenizer(input.readLine(), "[ ]");

            int startNode = Integer.parseInt(connectionInfo.nextToken());
            int endNode = Integer.parseInt(connectionInfo.nextToken());
            int cost = Integer.parseInt(connectionInfo.nextToken());

            Connection connection = new Connection(cost, startNode, endNode);
            costPriorityQueue.add(connection);

        }

        // 집합에 포함된 정점의 갯수와 최소 가중치 정보를 담을 변수 선언
        int totalCost = 0;
        int totalEdge = 0;

        // 집합 정보를 담을 배열 선언
        int[] groupInfo = new int[vertexNumber + 1];
        for (int i = 0; i < vertexNumber + 1; i++) {
            groupInfo[i] = i;
        }

        // Kruskal's Algorithm
        while (totalEdge < vertexNumber - 1 && !costPriorityQueue.isEmpty()) {

            // 가중치 순으로 확인
            Connection nowConnection = costPriorityQueue.poll();

            // 집합 관계를 확인하여 아직 집합이 아닌 경우 집합에 추가하고 가중치 가산
            if (!isUnion(groupInfo, nowConnection.start, nowConnection.end)) {
                makeUnion(groupInfo, nowConnection.start, nowConnection.end);
                totalEdge += 1;
                totalCost += nowConnection.cost;
            }

        }

        // 최종 최소 가중치값 출력
        output.write(Integer.toString(totalCost));

        output.flush();
        output.close();

    }

}