[백준] 1922번 네트워크 연결 (JAVA)

문제

https://www.acmicpc.net/problem/1922

1922번: 네트워크 연결

 

설명

각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 구해야 한다.

이번 문제에서는 크루스칼 알고리즘을 통해 최소 신장 트리를 구할 것이다.

먼저 간선의 정보를 저장할 Edge 클래스를 만든다.

우선순위 큐에서 가중치를 기준으로 오름차순으로 정렬하기 위해 Comparable 인터페이스를 이용한다.

static class Edge implements Comparable<Edge> {
    int current;
    int dest;
    int cost;

    public Edge(int current, int dest, int cost) {
        this.current = current;
        this.dest = dest;
        this.cost = cost;
    }

    @Override
    public int compareTo(Edge e) {
        return this.cost - e.cost;
    }
}

현재 우선순위 큐에는 가중치를 기준으로 오름차순으로 정렬되어 있을 것이다.

큐가 비어있을 때까지 큐에서 하나씩 꺼내어 간선의 두 정점이 같은 집합에 속해있는지 find 함수를 이용한다.

같은 집합에 속한다면 사이클이 있다고 판단하고 건너뛰고 아니라면 간선의 양 끝 정점을 union 한다.

int find(int element) {
    if (computers[element] == element)
        return element;
    else {
        return graph[element] = find(graph[element]);
    }
}
 
void union(int element1, int element2) {
    // element1과 element2의 대표 노드 확인
    int root1 = find(element1);
    int root2 = find(element2);
 
    // element1과 element2의 대표 노드가 다를 경우
    if (root1 != root2)
       graph[root1] = root2;
}
    
void kruskal() {
    int minCost = 0;
    
    while (!pq.isEmpty()) {
    	Edge edge = pq.poll();
        
        if (find(edge.current) != find(edge.dest)) {
            union(edge.current, edge.dest);
            minCost += edge.cost;
        }
    }
    
    System.out.println(minCost);
}

 

전체 코드

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

public class Main {

    static int N, M;
    static int[] computers;
    static PriorityQueue<Edge> pq;

    static class Edge implements Comparable<Edge> {
        int current;
        int dest;
        int cost;

        public Edge(int current, int dest, int cost) {
            this.current = current;
            this.dest = dest;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge e) {
            return this.cost - e.cost;
        }
    }

    static int find(int element) {
        if (computers[element] == element)
            return element;
        else {
            return computers[element] = find(computers[element]);
        }
    }

    static void union(int element1, int element2) {
        // element1과 element2의 대표 노드 확인
        int root1 = find(element1);
        int root2 = find(element2);

        // element1과 element2의 대표 노드가 다를 경우
        if (root1 != root2)
            computers[root1] = root2;
    }

    static void kruskal() {
        int minCost = 0;

        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            if (find(edge.current) != find(edge.dest)) {
                union(edge.current, edge.dest);
                minCost += edge.cost;
            }
        }

        System.out.println(minCost);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());

        computers = new int[N + 1];
        for (int num = 0; num <= N; num++) {
            computers[num] = num;
        }

        pq = new PriorityQueue<>();

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            pq.offer(new Edge(a, b, c));
        }

        kruskal();
    }
}