백준 14950번: 정복자 prim 알고리즘 - Java

https://www.acmicpc.net/problem/14950

14950번: 정복자

1.문제설명

도시를 정복하기 위해 MST를 만들어야 하는 문제이다.

 

주의할 점은 한 도시를 정복한 이후부터 간선의 가중치가 t값만큼 증가해야한다.

 

첫 도시를 정복할 때 가중치가 포함되면 안된다.

 

Java로 Prim 알고리즘을 구현하기 위해서

 

자바 우선순위큐를 사용할 줄 알아야한다.

 

이때 custom class를 이용하기 때문에 Comparable을 implements 해주어야 한다.

 

 

---

 

2.문제풀이코드 C++

import java.util.*;

class Edge implements Comparable<Edge>{
//    boolean canUse;
    int x, y;
    Edge(int x, int y){
//        canUse = true;
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "(" + x + "," + y + ")";
    }

    @Override
    public int compareTo(Edge edge){
        return Integer.compare(y, edge.y);
    }
}

public class Main {
    static int n,m,t;
    static boolean ch[];
    static ArrayList<Edge> adj[];


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        t = sc.nextInt();

        PriorityQueue<Edge> Q = new PriorityQueue<>();
        ch = new boolean[n+1];


        adj = new ArrayList[n+1];
        for(int i=0; i<=n; i++){
            adj[i] = new ArrayList<Edge>();
        }


        for(int i=0; i<m; i++){
            int a, b, c;
            a = sc.nextInt();
            b = sc.nextInt();
            c = sc.nextInt();
            adj[a].add(new Edge(b,c));
            adj[b].add(new Edge(a,c));
        }


        Q.add(new Edge(1,0));

        int cnt = 0;
        int ans = 0;
        while(!Q.isEmpty()){
            Edge cur = Q.poll();

            if(!ch[cur.x]){
                ch[cur.x] = true;
                ans += cur.y;
                cnt++;

                if(cnt>2){
                    ans += t*(cnt-2);
                }

//                System.out.println(ans);

                for(Edge nx : adj[cur.x]) {
                    if (ch[nx.x] == false) {
                        Q.add(nx);
                    }
                }
            }
        }

        System.out.println(ans);

    }
}