[SWEA] 1251. 하나로

최소신장트리 즉, MST를 구하는 문제이다.

최소신장트리란 , 그래프에서 V개의 접점과 E개의 간선이 있을 때, V-1개의 간선으로 이루어진 트리로 싸이클이 생겨나지 않고, 방향이 없으며 간선들의 합이 최소일 때를 말한다. 구하는 대표적인 알고리즘으로는 Kruskal, Prim이 있다.

※그래프
정점V 와 간선E로 이루어진 연결관계를 모아 놓은 자료. 프로그래밍상 표현법은 다음과 같다.
- 간선의 배열 : 정점과 정점의 연결정보인 간선을 모아놓음
- 인접 리스트 : 각 정점별로 연결된 정점의 정보를 모아놓음(ex. List[])
- 인접행렬 : 2차원 행렬에 각 정점과 정점간의 연결정보를 표시(ex. arr[][])

※Kruskal 알고리즘
그래프에서 간선을 기준으로 MST를 찾고 싶을 때 사용하는 알고리즘이다. 과정은 다음과 같다.
1. 그래프의 모든 간선들을 가중치의 오름차순으로 정렬 (PriorityQueue를 사용하면 간편)
2. 정렬된 간선리스트에서 가중치가 낮은 순선대로 싸이클을 형성하지 않는 간선 선택
   2-a. 가중치가 낮은 간선선택
   2-b. 싸이클이 형성된다면 다음 가중치의 간선 선택(싸이클 확인시 UnionFind사용)
3. 해당간선을 MST집합에 추가, 전체 선택된 간선이 V-1개 일때 까지 반복

※Prim 알고리즘
그래프에서 정점을 기준으로 MST를 찾고 싶을 때 사용하는 알고리즘이다. 과정은 다음과 같다.
1. 임의의 정점을 하나 선택해서 시작
2. 선택한 정점과 인접하는 정점들 중 최소 비용의 간선이 존재하는 정점(방문하지 않은 곳)을 선택
3. 모든 정점이 선택될 때까지 1,2 과정을 반복

하나로 문제는 간선을 기준으로 하는 Kruskal알고리즘을 선택하여 풀었고, UnionFind 함수를 같이 사용하여 해결하였다. UnionFind를 잠시 본다면 parents 배열을 이용하여 각 V마다 자기자신을 부모로 초기화해준다음, findSet() 함수로 주어진 V에 대한 부모를 찾을수 있게 해주었다. 또한, union()함수를 이용하여 하나의 부모로 합쳐주는 작업도 수행하였다. 

package swea;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
 
public class Solution_d4_1251_하나로 {
    
    static int[] parents;
    static int N;
    static List<Edge> list;
    
    static double env;
    
    static class Edge implements Comparable<Edge>{
        int v1;
        int v2;
        double weight;
        
        public Edge(int v1,int v2, double w) {
            this.v1=v1;this.v2=v2;weight=w;
        }
        
        @Override
        public int compareTo(Edge o) {
            return Double.compare(weight, o.weight);
        }
    }
    
    
    public static void main(String[] args) throws Exception {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int T=Integer.parseInt(br.readLine());
    
        for(int tc=1;tc<=T;tc++) {
            N=Integer.parseInt(br.readLine());
            
            int[] tempX=new int[N];
            st=new StringTokenizer(br.readLine());
            for(int i=0;i<N;i++)
                tempX[i]=Integer.parseInt(st.nextToken());
            
            int[] tempY=new int[N];
            st=new StringTokenizer(br.readLine());
            for(int i=0;i<N;i++)
                tempY[i]=Integer.parseInt(st.nextToken());
    
            env=Double.parseDouble(br.readLine());
            
            list=new ArrayList<>();
            
            for(int i=0;i<N-1;i++) {
                for(int j=i+1;j<N;j++) {
                    double dis = Math.pow(Math.abs(tempX[i]-tempX[j]), 2) 
                            + Math.pow(Math.abs(tempY[i]-tempY[j]), 2);
                    list.add(new Edge(i, j, dis));
                }
            }
            Collections.sort(list);
            
            parents=new int[N];
            for(int i=0;i<N;i++)
                parents[i]=i;
            
            
            double dis=0.0;
            int cnt=0;
            for(int i=0;i<list.size();i++) {
                int a=findSet(list.get(i).v1);
                int b=findSet(list.get(i).v2);
                
                if(a==b) {    //부모가 같으면 패스
                    continue;
                }
                
                union(a, b);
                
                dis+=list.get(i).weight;
                cnt++;
                if(cnt==N-1)
                    break;
            }
            
            double result= dis * env;
            
            System.out.println("#"+tc+" "+Math.round(result));
        }
    }
    
    static int findSet(int x) {
        if(x==parents[x])
            return x;
            
        parents[x]=findSet(parents[x]);
        return parents[x];
    }
    
    static void union(int x,int y) {
        int px = findSet(x);
        int py = findSet(y);
        
        if(px<py)
            parents[py]=px;
        else
            parents[px]=py;
            
    }
    
}