백준 JAVA 1992번 네트워크 연결

문제 링크: https://www.acmicpc.net/problem/1922

1922번: 네트워크 연결

 

 

해당 문제는 최소신장트리의 개념에 가중치가 생겨 모든 정점을 연결할 때 최소 비용을 구하는 문제다. 크루스칼 알고리즘 과 프림 알고리즘으로 해결이 가능하다.

 

find() 함수로 정점의 부모를 찾고 union() 함수로 부모가 다를 경우 부모를 같게 해주어 최소신장트리 조건을 만족시켜준다. 이때 PriorityQueue를 사용하여 가중치를 오름차순으로 정렬시켜준 후 작은 가중치 순서로 진행해준다.

 

 

import java.math.BigInteger;
import java.util.*;
import java.io.*;


class node implements Comparable<node>{
    int start;
    int end;
    int cost;

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

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

public class Main {

    static int n;
    static int m;
    static int [] parent;
    static int result;
    static PriorityQueue<node> queue = new PriorityQueue<>();
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n= Integer.parseInt(br.readLine());
        m=Integer.parseInt(br.readLine());

        parent = new int[n+1];

        for(int i=1; i<=n; i++){
            parent[i]=i;
        }

        int start;
        int end;
        int cost;

        for(int i=0; i<m; i++){
            String[] s = br.readLine().split(" ");
            start = Integer.parseInt(s[0]);
            end = Integer.parseInt(s[1]);
            cost = Integer.parseInt(s[2]);
            queue.add(new node(start,end,cost));
        }

        while(!queue.isEmpty()){
            node poll = queue.poll();

            if(!check(poll.start,poll.end)){
                union(poll.start,poll.end);
                result+=poll.cost;
            }
        }

        System.out.println(result);

    }


    private static int find(int x){
        if(x==parent[x]){
            return x;
        }
        else{
            return x=find(parent[x]);
        }
    }

    private static boolean check(int x, int y){
        x=find(x);
        y=find(y);

        if(x!=y){
            return false;
        }
        else{
            return true;
        }
    }

    private static void union(int x, int y){
        x= find(x);
        y= find(y);
        if(x!=y){
            parent[y]=x;
        }
    }


}