프림 - 원더랜드(최소스패닝트리 : 프림, PriorintyQueue 활용)

문제

원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다.
원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다. 도로를 공사하여 길을 최소비용으로 짓는 비용을 구하여라.

입력
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

풀이

class Load2 implements Comparable<Load2>{
    int v;
    int cost;

    public Load2(int v, int cost) {
        this.v = v;
        this.cost = cost;
    }
    @Override
    public int compareTo(Load2 o) {
        return this.cost - o.cost;
    }
}
public class ex8 {
    static int v,e;
    static int[] ch;
    static ArrayList<ArrayList<Load2>> graph;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        v = sc.nextInt();
        e = sc.nextInt();
        ch = new int[v+1];
        graph = new ArrayList<ArrayList<Load2>>();
        for(int i=0; i<=v; i++){
            graph.add(new ArrayList<Load2>());
        }

        for(int i=0; i<e; i++){
            int v1 = sc.nextInt();
            int v2 = sc.nextInt();
            int e = sc.nextInt();
            graph.get(v1).add(new Load2(v2,e));
            graph.get(v2).add(new Load2(v1,e));
        }

        //프림
        int answer=0;
        PriorityQueue<Load2> PQ = new PriorityQueue<>();
        PQ.offer(new Load2(1,0));
        while(!PQ.isEmpty()){
            Load2 tmp = PQ.poll();
            int v = tmp.v;
            if(ch[v]==0){
                ch[v]=1;
                answer+=tmp.cost;
                for(Load2 x : graph.get(v)){
                    if(ch[x.v]==0) PQ.offer(new Load2(x.v,x.cost));
                }
            }
        }
        System.out.println(answer);

    }
}

1. 양방향 그래프다. 인접리스트에 다 담아준다. 비용낮은 순으로 graph 정렬해준다.

2. 회로가 되면안되고 , 트리형태를 만들어야하기에, ch배열을이용한다. PQ.poll()한 정점의 ch[v]==0 이면 비용을 추가해주고 그 v에서 갈수있는 곳들을 forEach로 접근한다. 이때도 ch[x.v]로 확인해준다. 그렇게 PQ.Offer() 해준다.

개인 적으로 최소스패닝 트리를 구해야하는 문제는 Union&Find방식이 더 쉽고 좋은듯하다.