딩코딩 : Computer Science 블로그

https://www.acmicpc.net/problem/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값이 음수면 객체 본인이 작은 것이고

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

1. 추상 클래스 상속

abstract class Shape{
	public Shape(){}
    public void Paint(){draw();}
    abstract public void draw(); // 추상 메소드
}

abstract class Line extends Shape{ //추상 메소드 draw()를 상속 받았는데 구현을 하지 않으면 sub class 역시 추상 클래스가 된다
	public String toString(){
    	return "Line";
    }
}

자바에서 슈퍼클래스의 추상 메소드를 서브 클래스에서 구현하지 않으면,

서브 클래스 역시 슈퍼 클래스처럼 abstract 클래스가 된다.

적절한 비유는 아니지만

abstract를 빚으로 생각한다면

부모 클래스에 있는 abstract(빚) 메소드를 자식이 해결하지 못한다면

자식도 abstract class가 되어버린다.

(abstract class면 객체를 생성할 수 없다..) 

2. 추상 클래스 사용 이유

서브 클래스마다 다르게 구현해야 할 필요가 있는 메소드를 추상 메소드로 정의해준다.

abstract class Animal{
	abstract void bark();
}

class dog extends Animal{
	void bark(){
    	System.out.println("멍멍");
    }
}

class cat extends Animal{
	void bark(){
    	System.out.println("냐옹");
    }
}

class bird extends Animal{
	void bark(){
    	System.out.println("짹쨱");
    }
}

이런 느낌이다.

큰 프로그램의 객체지향 설계를 해줄 때 서브 클래스의 세부 내용을 각각 다르게 해주어야 할 경우

이런 식으로 추상 메소드를 이용해주면 깔끔하게 코드를 정리할 수 있다.