[JAVA] 알고리즘 : 그리디- 원더랜드 (크루스칼, 프림)

 

 

크루스칼

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Edge implements Comparable<Edge>{
    public int v1; // 정점 1
    public int v2; // 정점 2
    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; // 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 sc = new Scanner(System.in);
        int n = sc.nextInt(); // 정점 개수
        int m = sc.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++){
            // a도시와 b도시를 연결하는 비용 c
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.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);
    }
}

 

 

프림

import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

class Edge implements Comparable<Edge>{
    public int vex; // 정점
    public int cost; // 점점으로 가는데 드는 비용

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

    @Override
    public int compareTo(Edge ob){
        return this.cost - ob.cost; // cost 오름차순 정렬
    }
}
class Main{

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 정점 개수
        int m = sc.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 = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            // 무방향 그래프
            graph.get(a).add(new Edge(b,c)); // a 정점에서 b 정점으로 가는데 드는 비용 c
            graph.get(b).add(new Edge(a, c)); // b 정점에서 a 정점으로 가는데 드는 비용 c
        }

        int answer = 0;

        PriorityQueue<Edge> pq = new PriorityQueue<>(); // 최솟값 비용을 먼저 우선순위로

        pq.offer(new Edge(1, 0)); // 정점 1부터 넣음

        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와 연결된 정점들 탐색
                    if(ch[ob.vex] == 0) pq.offer(new Edge(ob.vex, ob.cost)); // 방문하지 않은 정점이라면 큐에 넣음
                }
            }
        }
        System.out.println(answer);
    }
}