[BOJ 1922, Java] Network Connection

Problem Link

BOJ 1922

Category

Graph Theory, Minimum Spanning Tree

Description

Introduction

Lately, I’ve been focusing solely on solving problems, which has made me feel like I’ve been neglecting the theory. So, I’d like to document my problem-solving process while briefly reviewing the theory.

MST (Minimum Spanning Tree)

• What is a spanning tree?

A spanning tree is a tree that contains every vertex in a graph.

• Minimum Spanning Tree (MST)

: The spanning tree with the shortest total edge length.

• Key Features

: It has (n - 1) edges passing through n vertices. : Since it minimizes edge length, it can be used for building internal networks, etc.

Prim’s Algorithm

• Select one initial vertex

• Sequentially select the shortest edge among those connected to vertices included in the MST

• Terminate when all vertices are connected

Kruskal's Algorithm

• Sort all edges by weight

• Sequentially add edges while ensuring no cycles are formed

• Terminate when all vertices are connected

Solution Code

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();

    }

}