원더랜드(최소스패닝트리-프림)

도시를 연결하는 도로의 최소비용 찾기

 

도시의 개수 V와 도로의 개수 E가 주어진다

 

입력

9 12
1 2 12
1 9 25
2 3 10
2 8 17
2 9 8
3 4 18
3 7 55
4 5 44
5 6 60
5 7 38
7 8 35
8 9 15

 

출력

196

 

프림 알고리즘 - 우선순위 큐를 이용해서 푸는 방법

 

이번에는 유니온 파인드를 하지 않고 우선순위 큐를 이용한다

Edge 클래스에 현재 정점이어진 정점과 비용만 넣고(입력을 받을때 이중 ArrayList에 get(현재정점).add(new Edge(이어진정점, 비용)) 형태로 받기에 Edge 클래스를 만들때 이어진 정점을 넣는다 현재 정점과 이어진 정점들을 탐색한다

check 배열을 만들어서 이미 정점을 방문했는지를 판단한다

 

class Edge implements Comparable<Edge>{
    int v, cost;

    //cost 순으로 오름차순 정렬
    @Override
    public int compareTo(Edge o) {
        return this.cost - o.cost;
    }

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

 static ArrayList<ArrayList<Edge>> graph = new ArrayList<ArrayList<Edge>>();

양방향이니 a->b 방향과 b->a 방향 모두 ArrayList에 넣어주자

for (int i =0; i < m; i++){
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            // 무방향이니 a->b와 b->a 둘다 된다, b->a 가는 것도 추가하자
            graph.get(a).add(new Edge(b,c));
            graph.get(b).add(new Edge(a,c));
        }

비용으로 오름차순 정렬된 우선순위 큐를 이용해서 pq에서 꺼낸 노드가 방문하지 않았으면 그 노드를 방문하고

그 노드와 연결된 노드들을 pq에 넣어주는 걸 반복한다

 

//cost 오름차순을 우선순위로 정렬하는 우선순위 큐
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(1,0));
        while (!pq.isEmpty()){
            Edge tmp = pq.poll();
            if (check[tmp.v] == 0){
                check[tmp.v] = 1;
                res += tmp.cost;
                for (Edge ob : graph.get(tmp.v)){
                    //이전에 방문한 노드를 다시 방문하지 않게 체크를 걸어줌
                    if (check[ob.v] == 0) pq.offer(new Edge(ob.v, ob.cost));
                }
            }
        }

 

전체 코드

import java.util.*;

class Edge implements Comparable<Edge>{
    int v, cost;

    //cost 순으로 오름차순 정렬
    @Override
    public int compareTo(Edge o) {
        return this.cost - o.cost;
    }

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

class Main{

    static int res = 0;
    static int[] check;
    static ArrayList<ArrayList<Edge>> graph;

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        check = new int[n+1];
        graph = new ArrayList<ArrayList<Edge>>();
        for (int i =0; i <= n; i++) graph.add(new ArrayList<Edge>());

        for (int i =0; i < m; i++){
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            // 무방향이니 a->b와 b->a 둘다 된다, b->a 가는 것도 추가하자
            graph.get(a).add(new Edge(b,c));
            graph.get(b).add(new Edge(a,c));
        }
        //cost 오름차순을 우선순위로 정렬하는 우선순위 큐
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(1,0));
        while (!pq.isEmpty()){
            Edge tmp = pq.poll();
            if (check[tmp.v] == 0){
                check[tmp.v] = 1;
                res += tmp.cost;
                for (Edge ob : graph.get(tmp.v)){
                    //이전에 방문한 노드를 다시 방문하지 않게 체크를 걸어줌
                    if (check[ob.v] == 0) pq.offer(new Edge(ob.v, ob.cost));
                }
            }
        }
        System.out.println(res);

    }
}