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

    }

}