swea 1251. [S/W 문제해결 응용] 4일차 - 하나로 Java (크루스칼)

문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15StKqAQkCFAYD 

SW Expert Academy

풀이

2021.12.15 - [알고리즘] - [알고리즘] 크루스칼(Kruskal)과 프림(Prim)

이번엔 최소 스패닝(신장) 트리(MST)문제이다.

MST란 모든 정점을 연결하는 간선들의 가중치의 합이 최소인 트리를 말하고,

이를 구하는 알고리즘으로는 대표적으로 크루스칼(Kruskal), 프림(Prim)알고리즘이 있다.

간단하게 Prim은 정점 중심으로 동작, 크루스칼은 간선 중심으로 동작하기 때문에 간선이 많을 때는 크루스칼이 아닌 프림 알고리즘을 선택하는 것이 옳다. 가끔 크루스칼은 통과 안 되고 프림은 통과하는 변태 같은 문제가 있다.

본인은 크루스칼로 풀었고 크루스칼은 유니온-파인드 알고리즘을 이용하여 구현할 수 있다. (프림은 다익스트라와 비슷)

풀이는 다음과 같다.

 

1. x,y좌표를 입력받아, 모든 간선들을 저장해놓는다.

2. 간선들을 가중치 기준 오름차순으로 정렬한다.

3.1 정렬된 간선 리스트를 순차적으로 이어준다.

3.2 이때 간선의 두 정점이 이미 이어져있다면 스킵한다.

//간선들이 가중치 기준 오름차순으로 정렬되었기 때문에, 모든 정점이 연결되기까지 가중치가 가장 작은 간선들만 사용
  했음을 보장한다.

 

코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
class Edge implements Comparable<Edge>{
    public long dis;
    public int from;
    public int to;
    Edge(long dis, int from, int to){
        this.from = from;
        this.dis = dis;
        this.to = to;
    }
     
    @Override
    public int compareTo(Edge edge) {
        if(this.dis < edge.dis) {
            return -1;
        }
        else if(this.dis > edge.dis) {
            return 1;
        }
        return 0;
    }
}
 
class Solution {
 
    static int n;
    static double E;
    static ArrayList<Edge> edge;
    static long answer=0;
    static long[] parent;
 
    static long getParent(long x) {
        if(parent[(int)x]==x) return x;
        else return parent[(int)x] = getParent(parent[(int)x]); 
    }
     
    static void unionParent(long a, long b) {
        a = getParent(a);
        b = getParent(b);
        if(a<b) {
            parent[(int)b] = a;
        }
        else {
            parent[(int)a] = b;
        }
    }
     
    static boolean findParent(long a, long b) {
        a = getParent(a);
        b = getParent(b);
        return a==b;
    }
    //크루스칼(유니온 파인드)
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            // input
            n =Integer.parseInt(br.readLine());
            StringTokenizer tk = new StringTokenizer(br.readLine());
            long[] x = new long[n];
            long[] y = new long[n];
            for(int i=0;i< n ; i++) {
                x[i] = Long.parseLong(tk.nextToken());
            }
            tk = new StringTokenizer(br.readLine());
            for(int i=0; i<n;i ++) {
                y[i] = Long.parseLong(tk.nextToken());
            }
            E = Double.parseDouble(br.readLine());
            parent = new long[n];
            for(int i=0; i< n ; i++) {
                parent[i] =i;
            }
            //간선 저장
            edge = new ArrayList<Edge>();
            for(int i=0; i<n;i++) {
                for(int j=i+1; j<n; j++) {
                    long dis = (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j]) * (y[i]-y[j]);
                    edge.add(new Edge(dis,i,j));    
                }
            }
            //간선 dis 기준 오름차순
            Collections.sort(edge);
             
            //solve
            for(Edge e : edge) {
                //연결되어있지 않다면
                if(!findParent(e.from, e.to)) {
                    unionParent(e.from, e.to);
                    answer+=e.dis;
                }
            }
            //output
            System.out.println("#" + t+" " + Math.round(E*answer));
             
            //reset
            answer=0;
        }
    }
}