백준 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;
        }
    }
 
 
}