원더랜드(크루스칼 : 최소 스패닝 트리)

 

모든 간선이 서로 연결되어있는 트리를 뽑아내는데 간선의 가중치 값이 최소가 되도록 만들어 내는 것이 최소 스패닝 트리 문제라고 한다.

작은 비용부터 정렬해놓고 작은 비용부터 선택해 나가면 된다!

 

선택을 할 때 회로만 되지 않는다면 된다! Union & Find로 회로 체크를 할 것!(함수 내용은 외우는게 좋다)

 

1.Union & Find 메서드 활용

import java.util.*;

class Edge implements Comparable<Edge>{
    public int v1;
    public int v2;
    public int cost;
    
    Edge(int v1, int v2, int cost) {
        this.v1 = v1;
        this.v2 = v2;
        this.cost = cost;
    }
    
    @Override
    public int compareTo(Edge ob){
        return this.cost-ob.cost;
    }
}

class Main {
    static int[] unf;

    public static int Find(int v){
        if(v==unf[v]) return v;
        else return unf[v]=Find(unf[v]);
    }

    public static void Union(int a, int b){
        int fa=Find(a);
        int fb=Find(b);
        if(fa!=fb) unf[fa]=fb;
    }

    public static void main(String[] args){
        Scanner kb = new Scanner(System.in);
        int n=kb.nextInt();
        int m=kb.nextInt();
        
        unf=new int[n+1];
        ArrayList<Edge> arr=new ArrayList<>();

        for(int i=1; i<=n; i++) unf[i]=i;

        for(int i=0; i<m; i++){
            int a=kb.nextInt();
            int b=kb.nextInt();
            int c=kb.nextInt();
            arr.add(new Edge(a, b, c));
        }

        int answer=0;

        Collections.sort(arr);

        for(Edge ob : arr){
            int fv1=Find(ob.v1);
            int fv2=Find(ob.v2);
            //두 정점이 같은 집합일때는 선택하면 안된다. 회로가 되어버리는 간선임!!!
            if(fv1!=fv2){
                answer+=ob.cost;
                Union(ob.v1, ob.v2);
            }
        }

        System.out.println(answer);
    }
}

트리에서 간선의 갯수는 정점의 갯수 - 1 이므로 cnt 변수 사용하여 좀 더 효율적으로 작성할 수 있음

트리를 이어줄 때 cnt를 증가시켜고 n-1이 되면 break;

 

2.PriorityQueue 활용

 

import java.util.*;

class Edge implements Comparable<Edge>{
    public int vex;
    public int cost;
    
    Edge(int vex, int cost) {
        this.vex = vex;
        this.cost = cost;
    }
    
    @Override
    public int compareTo(Edge ob){
        return this.cost-ob.cost;
    }
}

class Main {
    public static void main(String[] args){
        Scanner kb = new Scanner(System.in);
        int n=kb.nextInt();
        int m=kb.nextInt();
        ArrayList<ArrayList<Edge>> graph = new ArrayList<ArrayList<Edge>>();
        
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<Edge>());
        }
        
        int[] ch=new int[n+1];
        
        for(int i=0; i<m; i++){
            int a=kb.nextInt();
            int b=kb.nextInt();
            int c=kb.nextInt();
            graph.get(a).add(new Edge(b, c));
            graph.get(b).add(new Edge(a, c));
        }
        
        int answer=0;
        
        PriorityQueue<Edge> pQ = new PriorityQueue<>();
        
        pQ.offer(new Edge(1, 0));
        
        while(!pQ.isEmpty()){
            Edge tmp=pQ.poll();
            int ev=tmp.vex;
            //이거 체크 안해주면 회로가 되어버린다!!!
            if(ch[ev]==0){
                ch[ev]=1;
                answer+=tmp.cost;
                for(Edge ob : graph.get(ev)){
                    //ev와 연관된 간선들이 다 들어간다.
                    //1->2 에서 온걸 2->1로 보내버리면 안되므로 여기도 체크!
                    if(ch[ob.vex]==0) pQ.offer(new Edge(ob.vex, ob.cost));
                }
            }
        }
        
        System.out.println(answer);
    }
}