문제링크

백준 #1922. 네트워크 연결

풀이방법

"모든 컴퓨터를 연결하는데 필요한 최소비용"는 최소스패닝트리(Minimum Spanning Tree)의 간선 합을 구하라는 뜻이죠?(최소스패닝트리에 대한 간단한 설명은 풀이방법 하단을 참고해주세요) 저는 이 문제를 해결하기 위해 최소스패닝트리를 크루스칼 알고리즘(Kruskal's Algorithm)으로 구현했습니다!

크루스칼 알고리즘

#1. 간선 cost을 오름차순으로 sort
#2. 간선을 돌며 양쪽 정점의 컴포넌트가 다르면 두 컴포넌트를 연결
#3. 간선의 수가 n - 1이면 MST! else -> #2 진행

간단하죠? ㅎ-ㅎ #2에서 각 정점의 컴포넌트 확인 및 연결은 Union-Find를 이용했습니다~

+)최소스패닝트리: 트리의 간선마다 cost가 있을 때, 간선의 cost 합이 최소인 스패닝트리
+)스패닝트리: 그래프에서 간선의 수를 최소로 한 부분 그래프(n개의 정점 -> n - 1개의 최소 간선 수)

코드

import java.util.Arrays;
import java.util.Scanner;

public class NetworkConnection {
    static final int ROOT = -1;
    static int[] tree;
    static public void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        tree = new int[n];
        for (int i = 0; i < n; i++) tree[i] = ROOT;
        NetworkEdge[] networkEdges = new NetworkEdge[m];
        for (int i = 0; i < m; i++) {
            networkEdges[i] = new NetworkEdge(sc.nextInt() - 1, sc.nextInt() - 1, sc.nextInt());
        }
        Arrays.sort(networkEdges);

        int numOfEdges = 0;
        int sumOfCosts = 0;
        for (NetworkEdge edge: networkEdges) {
            if (merge(edge.pcA, edge.pcB)) {
                numOfEdges++;
                sumOfCosts += edge.cost;
            }

            if (numOfEdges == (n - 1)) break;
        }

        System.out.print(sumOfCosts);
    }

    static private int find(int pc) {
        if (tree[pc] == ROOT) return pc;
        else {
            tree[pc] = find(tree[pc]);
            return tree[pc];
        }
    }

    static private boolean merge(int pcA, int pcB) {
        int pcAHead = find(pcA);
        int pcBHead = find(pcB);

        if (pcAHead != pcBHead) {
            tree[pcBHead] = pcAHead;
            return true;
        } else return false;
    }
}

class NetworkEdge implements Comparable<NetworkEdge> {
    public int pcA;
    public int pcB;
    public int cost;

    public NetworkEdge(int pcA, int pcB, int cost) {
        this.pcA = pcA;
        this.pcB = pcB;
        this.cost = cost;
    }

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

🤓