백준 1368번 : 물대기 - Java

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

1368번: 물대기

import java.util.*;

class Edge implements Comparable<Edge>{
    int x, y, cost;

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

    @Override
    public int compareTo(Edge e){
        return cost - e.cost;
    }
}

public class Main {

    static int unf[];

    static int Find(int x){
        if(unf[x]==-1) return x;
        return unf[x] = Find(unf[x]);
    }

    static void Union(int a, int b){
        int a1 = Find(a);
        int b1 = Find(b);

        if(a1!=b1){
            unf[a1] = b1;
        }
    }

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

        ArrayList<Edge> list = new ArrayList<>();

        Collections.sort(list);

        int n = sc.nextInt();
        unf = new int[n+1];

        Arrays.fill(unf,-1);


        for(int i=1; i<=n; i++){
            int p = sc.nextInt();
            list.add(new Edge(0,i,p));
        }

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                int p = sc.nextInt();
                if(i==j) continue;
                list.add(new Edge(i,j,p));
            }
        }

        Collections.sort(list);

        int ans = 0;
        for(int i=0; i<list.size(); i++){
            Edge cur = list.get(i);
            int x = cur.x;
            int y = cur.y;
            int c = cur.cost;

            if(Find(x)!=Find(y)){
                Union(x,y);
                ans += c;
            }
        }

        System.out.println(ans);

    }
}

 

 

import java.util.*;

class Edge implements Comparable<Edge>{
    int x, y, cost;

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

    @Override
    public int compareTo(Edge e){
        return cost - e.cost;
    }
}

public class Main {

    static int unf[];

    static int Find(int x){
        if(unf[x]==-1) return x;
        return unf[x] = Find(unf[x]);
    }

    static void Union(int a, int b){
        int a1 = Find(a);
        int b1 = Find(b);

        if(a1!=b1){
            unf[a1] = b1;
        }
    }

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

        PriorityQueue<Edge> list = new PriorityQueue<>();

        int n = sc.nextInt();
        unf = new int[n+1];

        Arrays.fill(unf,-1);


        for(int i=1; i<=n; i++){
            int p = sc.nextInt();
            list.add(new Edge(0,i,p));
        }

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                int p = sc.nextInt();
                if(i==j) continue;
                list.add(new Edge(i,j,p));
            }
        }


        int ans = 0;
        while(!list.isEmpty()){
            Edge cur = list.poll();
            int x = cur.x;
            int y = cur.y;
            int c = cur.cost;

            if(Find(x)!=Find(y)){
                Union(x,y);
                ans += c;
            }
        }

        System.out.println(ans);

    }
}

 

 

compareTo의 return값이 음수면 객체 본인이 작은 것이고

양수면 객체 본인이 큰 것이다.